SPOJ QTREE Query on a tree VI

You are given a tree (an acyclic undirected connected graph) with n nodes. The tree nodes are numbered from 1 to n. Each node has a color, white or black. All the nodes are black initially. We will ask you to perform some instructions of the following form:

0 u: ask for how many nodes are connected to u, two nodes are connected if all the node on the path from u to v (inclusive u and v) have the same color.
1 u: toggle the color of u (that is, from black to white, or from white to black).

Input

The first line contains a number n that denotes the number of nodes in the tree (1 ≤ n ≤ 10⁵). In each of the following n-1 lines, there will be two numbers (u, v) that describes an edge of the tree (1 ≤ u, v ≤ n). The next line contains a numberm denoting number of operations we are going to process (1 ≤ m ≤ 10⁵). Each of the following m lines describe an operation (t, u) as we mentioned above(0 ≤ t ≤ 1, 1 ≤ u ≤ n).

Output

For each query operation, output the corresponding result.

Example

Input 1:
5

1 2

1 3

1 4

1 5

3

0 1

1 1

0 1

Output 1:
5

1


Input 2:
7

1 2

1 3

2 4

2 5

3 6

3 7

4

0 1

1 1

0 2

0 3



Output 2:
7

3

3

Warning: large input/output data,be careful with certain languages

改变某个点的颜色，或者询问与某点相连（两点路径上没有异色点）的同色点有多少个

树树链剖分+树状数组

首先需要一个方便的统计答案的方式。每个点开一个统计答案的变量，显然可行，但是更新麻烦。

考虑把一整块儿同色点的答案存储在它们中深度最浅的那个点上。若如此做，修改一个点的颜色时，只需要修改从该点到根的一条链上的答案。

如果有了树剖，存储答案就可以用线段树或者树状数组。听说线段树容易T，那就用树状数组咯。

修改一个点时，先找到从该点向上的最长同色链，整链减去答案，再改变颜色，再找到从该点向上的最长同色链，整链累加答案。

如何找最长同色链？

　　另开一个树状数组，记录链上某颜色点的数量的前缀和。如果整条重链上的某颜色点数量等于链长度，显然可以尝试继续上溯，否则说明同色链的最浅点在当前重链上，那么就在当前重链上二分判断。

如何记录答案？

　　脑洞了各种方法，最后发现比较方便的改法是，修改x的father到最浅点的father这条链（在前者上减去，在后者上累加），因为x上要存x以下的连通块的答案，方便颜色变回来时的累加，所以不能改。作为等价调整，需要在x的father上减。（类比DFS序问题的值维护）

无数次WA和RE，过程中重构了两次代码，无尽的debug。写这一道题花了近一整天时间。

前两份代码中，为了树状数组操作方便，树剖出的结点编号是倒着编号的。然而这样似乎在向下修改子结点时下标会出现0，使得树状数组爆炸。

最后借鉴别人的二分方式，并改成了正序编号，迷之解决了迷之问题

还有其他各种各样的毛病……

顺带一提，最后两小时时间找出的bug，是某一句调用树状数组的时候，把pos和co的位置写反了……

信心尽失，痛不欲生，好在最后还是过了。

 /*by SilverN*/

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 const int INF=1e8;

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

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

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

     return x*f;

 }

 struct edge{int v,nxt;}e[mxn<<];

 int hd[mxn],mct=;

 void add_edge(int u,int v){

     e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct;return;

 }

 int n,m;

 //

 int ct[][mxn];

 int col[mxn];

 void add(int p,int co,int v){

     while(p<=n){ct[co][p]+=v;p+=p&-p;}

     return;

 }

 int ask(int co,int p){

     int res=;

     while(p){res+=ct[co][p];p-=p&-p;}

     return res;

 }

 //

 struct node{

     int fa,son,top;int sz,w,e;

 }t[mxn];

 int dep[mxn];

 int id[mxn],cnt=;

 void DFS1(int u,int fa){

     t[u].sz=;dep[u]=dep[fa]+;

     for(int i=hd[u];i;i=e[i].nxt){

         if(e[i].v==fa)continue;int v=e[i].v;

         t[v].fa=u;

         DFS1(v,u);

         t[u].sz+=t[v].sz;

         if(t[v].sz>t[t[u].son].sz)t[u].son=v;

     }

     return;

 }

 void DFS2(int u,int top){

     t[u].w=++cnt;t[u].top=top;

     id[cnt]=u;

     if(t[u].son){

         DFS2(t[u].son,top);

         for(int i=hd[u];i;i=e[i].nxt){

             if(e[i].v==t[u].fa || e[i].v==t[u].son)continue;

             DFS2(e[i].v,e[i].v);

         }

     }

     t[u].e=cnt;

 }

 //

 int find(int L,int R,int co){//链上查询相连的同色最浅点

     int l=L,r=R,ans=;

     while(r<=l){//左边深右边浅

         int mid=(l+r)>>;

         int res=ask(co,l)-ask(co,mid-);

         if(res==l-mid+){

             ans=mid;l=mid-;

         }else r=mid+;

     }

     return ans;

 }

 int query(int x){//查询从x到y的链上的连续同色最浅点的树剖编号

     int cc=col[x];

     while(t[x].top!=){

         int tmp=ask(cc,t[x].w)-ask(cc,t[t[x].top].w-);

         if(tmp==t[x].w-t[t[x].top].w+){

             if(col[x]!=col[t[t[x].top].fa])return t[t[x].top].w;

             else x=t[t[x].top].fa;

         }

         else return find(t[x].w,t[t[x].top].w,cc);

     }

     return find(t[x].w,t[].w,cc);

 }

 void upd(int x,int y,int v,int c){

     while(t[x].top!=t[y].top){

         if(dep[t[x].top]<dep[t[y].top])swap(x,y);

         add(t[t[x].top].w,c,v);

         add(t[x].w+,c,-v);

         x=t[t[x].top].fa;

     }

     if(dep[x]>dep[y])swap(x,y);

     add(t[x].w,c,v);

     add(t[y].w+,c,-v);

     return;

 }

 void update(int x){

     int y=id[query(x)];

     if(x>)upd(t[y].fa,t[x].fa,-ask(col[x]+,t[x].w),col[x]+);

     add(t[x].w,col[x],-);

     col[x]^=;

     add(t[x].w,col[x],);

     y=id[query(x)];

     if(x>)upd(t[y].fa,t[x].fa,ask(col[x]+,t[x].w),col[x]+);

     return;

 }

 int main(){

 //    freopen("in.txt","r",stdin);

     int i,j,u,v;

     n=read();

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

         u=read();v=read();

         add_edge(u,v);

         add_edge(v,u);

     }

     DFS1(,);t[].fa=;//

 //    cnt=n+1;

     DFS2(,);

     for(i=;i<=n;i++){//初始化，全为黑色

         col[i]=;

         add(t[i].w,col[i]+,t[i].sz);

         add(t[i].w+,col[i]+,-t[i].sz);

         add(t[i].w,col[i],);

     }

     add(,,);

     m=read();int op,x;

     while(m--){

         op=read();x=read();

         if(op){//修改

             update(x);

         }

         else{//查询

             int y=id[query(x)];

             int ans=ask(col[x]+,t[y].w);

             printf("%d\n",ans);

         }

     }

     return ;

 }

巴特西

SPOJ QTREE Query on a tree VI

Input

Output

Example

最新文章

热门文章