Genealogy in the trees

感觉题解太智力了，写个不带脑子的大暴力 做法。

给定 个点对， 次询问，对每次询问的点对 查询有多少 点对 满足 是 的祖先， 是 的祖先。

树上问题考虑转换成序列问题，先转换到dfs序上。

考虑拆解查询，满足 是 的祖先这个条件在重链剖分之后是 段区间，满足 是 的祖先这个条件是一段连续区间，所以把一次询问拆成 次互不相交的询问最后相加即可。

现在问题转换成了，二维平面中有 个点与 个矩形，求每个矩形覆盖了多少点。这是一个经典问题直接离线询问即可。通过一个简单的单点加，区间询问的线段树即可在 时间内通过。

（赛时我的代码是拆 个点，转化成矩阵加1，单点求值。但是本质相同。）

#include <bits/stdc++.h>
//efine int long long
#define endl '\n'
#define mid ((l+r)/2)
#define ls rt<<1
#define rs rt<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
using namespace std;
const string yes="YES\n",no="NO\n";
const int inf=1e18;
int n,q,m,ans[300005];
vector <pair<int,int>>ask[300005];
struct seg_tree{
    vector<int>tr,lazy,sz;
    seg_tree(){}
    seg_tree(int n):tr(n<<2),lazy(n<<2){}
    void push_up(int rt){tr[rt]=tr[ls]|tr[rs];}
    void build(int rt,int l,int r){
        lazy[rt]=0;tr[rt]=0;
        if(l==r){return;}
        build(lson);build(rson);
        push_up(rt);
    }
    void push_down(int rt){
        if(lazy[rt]){
            tr[ls]+=lazy[rt];tr[rs]+=lazy[rt];
            lazy[ls]+=lazy[rt];lazy[rs]+=lazy[rt];
            lazy[rt]=0;
        }
    }
    void update(int rt,int l,int r,int ql,int qr,int k){
        //cout<<q<<":"<<rt<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<" "<<k<<endl;
        if(ql<=l&&r<=qr){tr[rt]+=k;lazy[rt]+=k;return;}
        push_down(rt);
        if(mid>=ql) update(lson,ql,qr,k);
        if(mid<qr) update(rson,ql,qr,k);
        push_up(rt);
    }
    int ask(int rt,int l,int r,int x){
        if(l==r)return tr[rt];
        push_down(rt);
        if(mid>=x)return ask(lson,x);
        else return ask(rson,x);
    }
}seg;
#undef mid
vector<int>p[500005];
int dfn[300005],sz[300005],pr[300005],dep[300005],fa[300005];
int lst[300005];
int cnt,root,mo;
void dfs1(int u){
    if(fa[u]!=0) p[u].erase(find(p[u].begin(),p[u].end(),fa[u]));
    sz[u]=1;
    for(auto v:p[u]){
        if(v==fa[u])continue;
        fa[v]=u;
        dep[v]=dep[u]+1;
        dfs1(v);
        sz[u]+=sz[v];
    }
    sort(p[u].begin(),p[u].end(),[](const int x,const int y){return sz[x]>sz[y];});
}
void dfs2(int u){
    dfn[u]=++cnt;
    for(auto v:p[u]){
        if(v==p[u][0]){pr[v]=pr[u];}
        else{pr[v]=v;}
        dfs2(v);
    }
    lst[u]=cnt;
}
struct node{
    int l,r,op;
};
vector<node>cg[300005];
void solve(){
    cin>>n>>m>>q;
    root=1;
    seg=seg_tree(n);
    seg.build(1,1,n);
    for(int i=2;i<=n;i++){
        int u,v;cin>>u>>v;
        p[u].push_back(v);
        p[v].push_back(u);
    }
    dfs1(root);
    dfs2(root);
    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        while(y){
            cg[dfn[x]].push_back({dfn[pr[y]],dfn[y],1});
            cg[lst[x]+1].push_back({dfn[pr[y]],dfn[y],-1});
            y=fa[pr[y]];
        }
    }
    for(int i=1;i<=q;i++){
        int x,y;cin>>x>>y;
        ask[dfn[x]].push_back({dfn[y],i});
    }
    for(int i=1;i<=n;i++){
        for(auto[l,r,k]:cg[i]){
            seg.update(1,1,n,l,r,k);
        }
        for(auto [x,id]:ask[i]){
            ans[id]=seg.ask(1,1,n,x);
        }
    }
    for(int i=1;i<=q;i++){
        cout<<ans[i]<<endl;
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    solve();
}