题解 P3459 【[POI2007]MEG-Megalopolis】

这题有个很好的性质就是一棵树 还有就是父节点一定小于子节点所以我们可以很好的判断谁是子节点 询问求的是有几个父节点被覆盖过了 大概就是dfs序一波之后再树状数组上差分一下 ```cpp #include<bits/stdc++.h> using namespace std; int n,x,y,f[2000000],d[2000000],last[2000000],a[2000000][2],l[2000000],r[2000000],k,kk,q; char c; inline int read(){ char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar(); int k=1,kk=0;if (c=='-')k=-1;else kk=c-'0';c=getchar(); while (c>='0'&&c<='9')kk=kk*10+c-'0',c=getchar();return k*kk; }void doit(int x,int y){a[++kk][0]=last[x];a[kk][1]=y;last[x]=kk;} void dfs(int x,int fa,int de){ d[x]=de;l[x]=++k;for (int i=last[x];i;i=a[i][0]) if (a[i][1]!=fa)dfs(a[i][1],x,de+1); r[x]=k; } void putit(int x,int y){for (;x<=1000000;x+=x&(-x))f[x]+=y;} int findit(int x){int ans=0;for (;x;x-=x&(-x))ans+=f[x];return ans;} int main(){ n=read();for (int i=1;i<n;i++){ x=read();y=read();if (x>y)swap(x,y); doit(x,y); }dfs(1,0,0);q=read();while (q){ c=getchar();while (c!='W'&&c!='A')c=getchar(); if (c=='W'){ x=read();q--;//q次送信所以。。 printf("%d\n",d[x]-findit(l[x])); }else{ x=read();y=read();if (x>y)swap(x,y); putit(l[y],1);putit(r[y]+1,-1); } } } ```