首页 > 代码库 > BZOJ1103[POI2007]大都市meg 题解

BZOJ1103[POI2007]大都市meg 题解

题目大意:

  有一棵树,最先每条边的权值是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     }scanf("%d",&n);56     return 0;57 }

 

BZOJ1103[POI2007]大都市meg 题解