suoi14 子树查找 (dfs)

把询问记下来，然后开个桶差分
 1 #include<bits/stdc++.h>
 2 #define pa pair<int,int>
 3 #define lowb(x) ((x)&(-(x)))
 4 #define REP(i,n0,n) for(i=n0;i<=n;i++)
 5 #define PER(i,n0,n) for(i=n;i>=n0;i--)
 6 #define MAX(a,b) ((a>b)?a:b)
 7 #define MIN(a,b) ((a<b)?a:b)
 8 #define CLR(a,x) memset(a,x,sizeof(a))
 9 #define rei register int
10 using namespace std;
11 typedef long long ll;
12 const int maxn=1e6+10;
13 
14 inline ll rd(){
15     ll x=0;char c=getchar();int neg=1;
16     while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();}
17     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
18     return x*neg;
19 }
20 
21 int N,v[maxn],q[maxn];
22 int ch[maxn],hd[maxn];
23 int cnt[maxn],ans[maxn];
24 
25 void dfs(int x,int f){
26     int cc=cnt[q[x]];cnt[v[x]]++;
27     for(int i=hd[x];i;i=ch[i]){
28         if(i==f) continue;
29         dfs(i,x);
30     }ans[x]=cnt[q[x]]-cc;
31 }
32 
33 int main(){
34     //freopen(".in","r",stdin);
35     rei i,j,k;
36     N=rd();
37     for(i=1;i<=N;i++) v[i]=rd(),q[i]=rd();
38     for(i=2;i<=N;i++){
39         int a=rd();
40         ch[i]=hd[a];hd[a]=i;
41     }
42     dfs(1,0);
43     for(i=1;i<=N;i++) printf("%d
",ans[i]);
44     return 0;
45 }