SP16549 QTREE6 - Query on a tree VI（LCT）

题意翻译

题目描述

给你一棵n个点的树，编号1~n。每个点可以是黑色，可以是白色。初始时所有点都是黑色。下面有两种操作请你操作给我们看：

0 u：询问有多少个节点v满足路径u到v上所有节点（包括）都拥有相同的颜色

1 u：翻转u的颜色

输入格式

一行一个整数n

接下来n-1行，每行两个整数表示一条边

接下来一行一个整数m表示操作次数

接下来m行，每行两个整数分别表示操作类型和被操作节点输出格式

对每个询问操作输出相应的结果

题解

简单来说，就是维护同色联通块的大小

干脆直接暴力linkcut好了（T上天）

然后来介绍一下（刚学会的）一种维护染色联通块的较为常用的模型

很多与树有关的题目，当边权不好处理时，可以把边权转化为儿子的点权来做

然后这里恰恰相反，要把点权给转化为边权

我们把每一个节点的颜色赋给与它父亲相连的边

弄两个LCT，对应两种颜色，一种颜色的边只有在对应的LCT中才会相连

于是，同色的联通块，就转化为了减去顶部节点后的边的连通块（因为顶部节点在这个LCT是没有向上连边的，说明顶部节点并不是这个颜色，那么他的所有子树并不连通，要断开才行）

然后可以发现，修改点的颜色之后，只要在原来的LCT中cut，在新的LCT上link就行啦

查询怎么做呢？先access，然后findroot，再输出root的实子树大小就行了

ps：1本来没有父亲，但为了方便，可以建一个虚点n+1，令他作为1的父亲就好了

 //minamoto

 #include<iostream>

 #include<cstdio>

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 char sr[<<],z[];int C=-,Z;

 inline void Ot(){fwrite(sr,,C+,stdout),C=-;}

 inline void print(int x){

     if(C><<)Ot();if(x<)sr[++C]=,x=-x;

     while(z[++Z]=x%+,x/=);

     while(sr[++C]=z[Z],--Z);sr[++C]='\n';

 }

 const int N=;

 int f[N],Next[N<<],head[N],ver[N<<],tot,col[N],n,m;

 inline void add(int u,int v){

     ver[++tot]=v,Next[tot]=head[u],head[u]=tot;

     ver[++tot]=u,Next[tot]=head[v],head[v]=tot;

 }

 struct LCT{

     int fa[N],ch[N][],si[N],sum[N];

     LCT(){for(int i=;i<=n+;++i) sum[i]=;}

     inline bool isroot(int x){return ch[fa[x]][]!=x&&ch[fa[x]][]!=x;}

     #define lc ch[x][0]

     #define rc ch[x][1]

     inline void pushup(int x){sum[x]=sum[lc]+sum[rc]+si[x]+;}

     void rotate(int x){

         int y=fa[x],z=fa[y],d=ch[y][]==x;

         if(!isroot(y)) ch[z][ch[z][]==y]=x;

         fa[x]=z,fa[y]=x,fa[ch[x][d^]]=y,ch[y][d]=ch[x][d^],ch[x][d^]=y,pushup(y);

     }

     void splay(int x){

         for(int y=fa[x],z=fa[y];!isroot(x);y=fa[x],z=fa[y]){

             if(!isroot(y))

             ((ch[y][]==x)^(ch[z][]==y))?rotate(x):rotate(y);

             rotate(x);

         }

         pushup(x);

     }

     void access(int x){

         for(int y=;x;x=fa[y=x]){

             splay(x);

             si[x]+=sum[rc];

             si[x]-=sum[rc=y];

         }

     }

     int findroot(int x){

         access(x),splay(x);

         while(lc) x=lc;

         splay(x);

         return x;

     }

     void link(int x){

         access(x),splay(x);

         int y=fa[x]=f[x];

         access(y),splay(y);

         si[y]+=sum[x],sum[y]+=sum[x];

     }

     void cut(int x){

         access(x),splay(x);

         lc=fa[lc]=;

         pushup(x);

     }

 }lct[];

 void dfs(int u){

     for(int i=head[u];i;i=Next[i]){

         int v=ver[i];

         if(v==f[u]) continue;

         f[v]=u,dfs(v),lct[].link(v);

     }

 }

 int main(){

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

     n=read();

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

         int u=read(),v=read();

         add(u,v);

     }

     dfs();

     f[]=n+,lct[].link();

     m=read();

     while(m--){

         int op=read(),u=read();

         if(op) lct[col[u]].cut(u),lct[col[u]^=].link(u);

         else{

             int v=lct[col[u]].findroot(u);

             print(lct[col[u]].sum[lct[col[u]].ch[v][]]);

         }

     }

     Ot();

     return ;

 }

巴特西

SP16549 QTREE6 - Query on a tree VI（LCT）

题意翻译

最新文章

热门文章