BZOJ1103[POI2007]大都市meg 题解

题目大意：

　　有一棵树，最先每条边的权值是1，然后给出n+m-1个操作，操作有两种：1.询问一个点到根的路径上的权值和；2.将一条边的权值改为0.

思路：

　　用dfs序将树化为序列，在dfs序中我们会保存节点i进入时间come[i]和出去时间leave[i]，这两个数之间的区间即为其子树。询问实为前缀和，可用树状数组记录。修改只会影响其子树（即区间），其他部分并不会改变（+1-1抵消了）。

代码：

 #include<cstdio>

 #include<iostream>

 #define M 300000

 using namespace std;

 int n,m,cnt,dfn,to[M],next[M],head[M],c[M],come[M],leave[M];

 int read()

 {

     int x=,y=;

     char ch=getchar();

     while (ch<'' || ch>'') {if (ch=='-') y=-;ch=getchar();}

     while (ch>='' && ch<='') {x=x*+ch-;ch=getchar();}

     return x*y;

 }

 void ins(int x,int y)

 {

      to[++cnt]=y,next[cnt]=head[x],head[x]=cnt;

 }

 void dfs(int x)

 {

      come[x]=++dfn;

      for (int i=head[x];i;i=next[i]) dfs(to[i]);

      leave[x]=dfn;

 }

 void add(int x,int y)

 {

      for (;x<=n;x+=x&-x) c[x]+=y;

 }

 int sum(int x)

 {

     int ans=;

     for (;x;x-=x&-x) ans+=c[x];

     return ans;

 }

 int main()

 {

     int i,j,x,y;

     n=read();

     for (i=;i<n;i++) x=read(),y=read(),ins(x,y);

     dfs();

     m=read();

     for (i=;i<=n;i++) add(come[i],),add(leave[i]+,-);

     for (i=;i<n+m;i++)

     {

         char ch=getchar();

         while (ch<'A' || ch>'Z') ch=getchar();

         if (ch=='W') printf("%d\n",sum(come[read()]));

         else x=read(),y=read(),add(come[y],-),add(leave[y]+,);

     }     return ;

 }