P8575 「DTOI-2」星之河 求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=200007;
int n,f[MAXN];
int ee[MAXN<<1],h[MAXN<<1],hd[MAXN<<1],cnt;
struct node{
    int a,b,dfn;
    int id;
}e[MAXN];
int tot,ans[MAXN];
void add(int a,int b){
    ee[++cnt]=b;
    hd[cnt]=h[a];
    h[a]=cnt;
}
void dfs(int rt,int fa){
    e[rt].dfn=++tot;
    f[rt]=1;
    for(int i=h[rt];i;i=hd[i]){
        if(ee[i]==fa) continue;
        dfs(ee[i],rt);
        f[rt]+=f[ee[i]];
    }
}
bool cmp(node x,node y){
    return x.a<y.a;
}
bool Cmp(node x,node y){
    return x.b<y.b;
}
int tree[MAXN];
void modify(int x,int c){
    for(;x<=n;x+=(x&-x)) tree[x]+=c;
}
int query(int x){
    int res=0;
    for(;x;x-=(x&-x)) res+=tree[x];
    return res;
}
void Cdq(int l,int r){
    if(l==r) return ;
    int mid=(l+r)>>1;
    Cdq(l,mid);
    Cdq(mid+1,r);
    sort(e+l,e+1+mid,Cmp);
    sort(e+mid+1,e+1+r,Cmp);
    int j=l;
    for(int i=mid+1;i<=r;i++){
        while(j<=mid and e[i].b>=e[j].b){
            modify(e[j].dfn,1);
            j++;
        }
        ans[e[i].id]+=query(e[i].dfn+f[e[i].id]-1)-query(e[i].dfn);
    }
    for(int i=l;i<j;i++) modify(e[i].dfn,-1);
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%lld%lld",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs(1,-1);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&e[i].a,&e[i].b);
        e[i].id=i;
    }
    sort(e+1,e+1+n,cmp);
    Cdq(1,n);
    for(int i=1;i<=n;i++){
        if(ans[i]) printf("%lld\n",ans[i]);
    }
    return 0;
}