题目大意：
有一棵树，最先每条边的权值是1，然后给出n+m-1个操作，操作有两种：1.询问一个点到根的路径上的权值和；2.将一条边的权值改为0.
思路：
用dfs序将树化为序列，在dfs序中我们会保存节点i进入时间come[i]和出去时间leave[i]，这两个数之间的区间即为其子树。询问实为前缀和，可用树状数组记录。修改只会影响其子树（即区间），其他部分并不会改变（+1-1抵消了）。
代码：
1 #include<cstdio> 2 #include<iostream> 3 #define M 300000 4 using namespace std; 5 6 int n,m,cnt,dfn,to[M],next[M],head[M],c[M],come[M],leave[M]; 7 8 int read() 9 { 10 int x=0,y=1; 11 char ch=getchar(); 12 while (ch<'0' || ch>'9') {if (ch=='-') y=-1;ch=getchar();} 13 while (ch>='0' && ch<='9') {x=x*10+ch-48;ch=getchar();} 14 return x*y; 15 } 16 17 void ins(int x,int y) 18 { 19 to[++cnt]=y,next[cnt]=head[x],head[x]=cnt; 20 } 21 22 void dfs(int x) 23 { 24 come[x]=++dfn; 25 for (int i=head[x];i;i=next[i]) dfs(to[i]); 26 leave[x]=dfn; 27 } 28 29 void add(int x,int y) 30 { 31 for (;x<=n;x+=x&-x) c[x]+=y; 32 } 33 34 int sum(int x) 35 { 36 int ans=0; 37 for (;x;x-=x&-x) ans+=c[x]; 38 return ans; 39 } 40 41 int main() 42 { 43 int i,j,x,y; 44 n=read(); 45 for (i=1;i<n;i++) x=read(),y=read(),ins(x,y); 46 dfs(1); 47 m=read(); 48 for (i=2;i<=n;i++) add(come[i],1),add(leave[i]+1,-1); 49 for (i=1;i<n+m;i++) 50 { 51 char ch=getchar(); 52 while (ch<'A' || ch>'Z') ch=getchar(); 53 if (ch=='W') printf("%d\n",sum(come[read()])); 54 else x=read(),y=read(),add(come[y],-1),add(leave[y]+1,1); 55 }56 return 0; 57 }
转载于:https://www.cnblogs.com/HHshy/p/5823364.html
相关资源：JAVA上百实例源码以及开源项目