文档章节

SP16549 QTREE6 - Query on a tree VI(LCT)

o
 osc_4nmshwhm
发布于 2018/08/07 12:57
字数 1131
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

题意翻译

题目描述

给你一棵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的父亲就好了

  1 //minamoto
  2 #include<iostream>
  3 #include<cstdio>
  4 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
  5 char buf[1<<21],*p1=buf,*p2=buf;
  6 inline int read(){
  7     #define num ch-'0'
  8     char ch;bool flag=0;int res;
  9     while(!isdigit(ch=getc()))
 10     (ch=='-')&&(flag=true);
 11     for(res=num;isdigit(ch=getc());res=res*10+num);
 12     (flag)&&(res=-res);
 13     #undef num
 14     return res;
 15 }
 16 char sr[1<<21],z[20];int C=-1,Z;
 17 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
 18 inline void print(int x){
 19     if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
 20     while(z[++Z]=x%10+48,x/=10);
 21     while(sr[++C]=z[Z],--Z);sr[++C]='\n';
 22 }
 23 const int N=100005;
 24 int f[N],Next[N<<1],head[N],ver[N<<1],tot,col[N],n,m;
 25 inline void add(int u,int v){
 26     ver[++tot]=v,Next[tot]=head[u],head[u]=tot;
 27     ver[++tot]=u,Next[tot]=head[v],head[v]=tot;
 28 }
 29 struct LCT{
 30     int fa[N],ch[N][2],si[N],sum[N];
 31     LCT(){for(int i=1;i<=n+1;++i) sum[i]=1;}
 32     inline bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
 33     #define lc ch[x][0]
 34     #define rc ch[x][1]
 35     inline void pushup(int x){sum[x]=sum[lc]+sum[rc]+si[x]+1;}
 36     void rotate(int x){
 37         int y=fa[x],z=fa[y],d=ch[y][1]==x;
 38         if(!isroot(y)) ch[z][ch[z][1]==y]=x;
 39         fa[x]=z,fa[y]=x,fa[ch[x][d^1]]=y,ch[y][d]=ch[x][d^1],ch[x][d^1]=y,pushup(y);
 40     }
 41     void splay(int x){
 42         for(int y=fa[x],z=fa[y];!isroot(x);y=fa[x],z=fa[y]){
 43             if(!isroot(y))
 44             ((ch[y][1]==x)^(ch[z][1]==y))?rotate(x):rotate(y);
 45             rotate(x);
 46         }
 47         pushup(x);
 48     }
 49     void access(int x){
 50         for(int y=0;x;x=fa[y=x]){
 51             splay(x);
 52             si[x]+=sum[rc];
 53             si[x]-=sum[rc=y];
 54         }
 55     }
 56     int findroot(int x){
 57         access(x),splay(x);
 58         while(lc) x=lc;
 59         splay(x);
 60         return x;
 61     }
 62     void link(int x){
 63         access(x),splay(x);
 64         int y=fa[x]=f[x];
 65         access(y),splay(y);
 66         si[y]+=sum[x],sum[y]+=sum[x];
 67     }
 68     void cut(int x){
 69         access(x),splay(x);
 70         lc=fa[lc]=0;
 71         pushup(x);
 72     }
 73 }lct[2];
 74 void dfs(int u){
 75     for(int i=head[u];i;i=Next[i]){
 76         int v=ver[i];
 77         if(v==f[u]) continue;
 78         f[v]=u,dfs(v),lct[0].link(v);
 79     }
 80 }
 81 int main(){
 82     //freopen("testdata.in","r",stdin);
 83     n=read();
 84     for(int i=1;i<n;++i){
 85         int u=read(),v=read();
 86         add(u,v);
 87     }
 88     dfs(1);
 89     f[1]=n+1,lct[0].link(1);
 90     m=read();
 91     while(m--){
 92         int op=read(),u=read();
 93         if(op) lct[col[u]].cut(u),lct[col[u]^=1].link(u);
 94         else{
 95             int v=lct[col[u]].findroot(u);
 96             print(lct[col[u]].sum[lct[col[u]].ch[v][1]]);
 97         }
 98     }
 99     Ot();
100     return 0;
101 }

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Java知识回顾-基础知识(1)

面向对象和面向过程的区别 1 面向过程性能较高(面向过程语言大多是直接编译成计算机可读的机械码可直接运行) 2 面向对象易维护,易复用,易扩展(因为有封装,继承,多态可设计低耦合系统),面向对...

心田已荒
37分钟前
11
0
Vimium不使用鼠标离开地址栏的方法

使用chrome 的 Vimium 扩展也有很长一段时间了,最大的好处是可以在浏览器使用 vim 下的热键,告别鼠标和触控板也能愉快玩耍。 虽然大部分时间都使用cmd+O打开 URL或者历史,但有时候还是要用...

FalconChen
41分钟前
27
0
数据库周刊31丨openGauss 正式开源;7月数据库排行榜发布;PG解决社保问题;mysqlbinlog解析……

摘要:墨天轮数据库周刊第31期发布啦,每周1次推送本周数据库相关热门资讯、精选文章、干货文档。本周分享 华为openGauss 正式开源;7月数据库排行榜发布;浙江移动国产数据库AntDB迁移;抢鲜...

墨天轮小助手
44分钟前
10
0
婚礼行业小程序新玩法

现在婚礼行业越来越吃香,随之而来的婚庆公司、个人工作室都涌入市场。消费者可选择的越来越多,货比三家。婚礼公司都在绞尽脑汁加大推广力度,做各种优惠活动,来吸引消费者,提升销量。今天...

LOVEer1
46分钟前
9
0
Linux Ubuntu 14 Audit 系统审计服务

一、概述 系统等保要求,必须做系统审计服务,审计的目的是基于事先配置的规则生成日志,记录可能发生在系统上的事件,这里直接使用第三方插件 Audit,不用系统自带的审计服务日志。 (如需要...

华山猛男
56分钟前
22
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部