题解：P14436 [JOISC 2013] 间谍 / Spy

· · 题解

闲话

大手子很早就过了，但是我没有，所以被嘲讽了。

正文

形式化题意

题目又臭又长，简化一下。

给你两棵有根树 Tree_{j} 和 Tree_{i}，都有 N 个节点，但是可能不同构，两棵树间点的对应关系是 i_{1} 对 j_{1}，i_{2} 对 j_{2}，以此类推，就是一一对应。

现在给你 M 次操作，每次操作将给你两个点 R_{j} 和 S_{i}，每次求多少个 Tree_{i} 上的点满足：

最后问你，Tree_{i} 上的每个点共满足多少次。

思路

一般来说，对于树上问题，凡是有关子树的，都可以想到用 DFS 序来解决，所以接下来我们定义：

根据 DFS 序的优良性质，我们可以发现对于每次操作，满足条件的点 i 都可以转化成下面的条件：

这长得很像二维偏序，所以我们考虑把问题放到二维平面上来。

定义点 i 在二维平面上的对应坐标为 (dfn1_{i},dfn2_{i})，则我们可以发现每次操作等价于在二维平面上将点 R 和 S 之间的矩形贡献全部加一，就是区间修改。而每次的查询就是问点 i 即 (dfn1_{i},dfn2_{i}) 在二维平面上被计算了几次。

这明显是二维差分，不过我用的是二维树状数组因为有人用了差分，时间为 \Theta(m\times \log ^{2}n+n\times \log ^{2}n)，可以通过。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define V vector
#define FOR(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define pb push_back
const int INF=1e9+10;
struct BIT2{//二维差分树状数组 
    int n;V<V<int> >t;
    BIT2(int _n):n(_n+2),t(_n+3,V<int>(_n+3)){}
    #define lb(x) ((x)&(-x))
    void add(int x,int y,int w){
        for(int i=x;i<=n;i+=lb(i)){
            for(int j=y;j<=n;j+=lb(j)) t[i][j]+=w;
        }
    }
    void update(int a,int b,int x,int y,int w){//(a,b)到(x,y)（左上到右下）整体加w 
        add(a,b,w);
        add(a,y+1,-w);
        add(x+1,b,-w);
        add(x+1,y+1,w);
    }
    int query(int x,int y){//单点查询 
        int ans=0;
        for(int i=x;i;i-=lb(i)){
            for(int j=y;j;j-=lb(j)) ans+=t[i][j];
        }
        return ans;
    }
    #undef lb
};
int num=0;
void dfs(int u,int fa,V<V<int> >&e,V<int>&dfn,V<int>&siz){
    dfn[u]=++num;
    siz[u]=1;
    for(int v:e[u]){
        if(v==fa)continue;
        dfs(v,u,e,dfn,siz);
        siz[u]+=siz[v];
    }
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m;cin>>n>>m;
    BIT2 lls(n);
    V<V<int> >e1(n+1),e2(n+1);
    int root1=-1,root2=-1;
    FOR(i,1,n){
        int fa1,fa2;cin>>fa1>>fa2;
        if(fa1==0) root1=i;
        else e1[fa1].pb(i),e1[i].pb(fa1);
        if(fa2==0) root2=i;
        else e2[fa2].pb(i),e2[i].pb(fa2);
    }
    V<int>dfn1(n+1),dfn2(n+1),siz1(n+1),siz2(n+1);
    dfs(root1,0,e1,dfn1,siz1);num=0;
    dfs(root2,0,e2,dfn2,siz2);
    FOR(i,1,m){
        int r,s;cin>>r>>s;
        lls.update(dfn1[r],dfn2[s],dfn1[r]+siz1[r]-1,dfn2[s]+siz2[s]-1,1);
    }
    FOR(i,1,n){
        cout<<lls.query(dfn1[i],dfn2[i])<<"\n";
    }
    return 0;
}