首页 > 代码库 > 【BZOJ4817】【SDOI2017】树点涂色 [LCT][线段树]
【BZOJ4817】【SDOI2017】树点涂色 [LCT][线段树]
树点涂色
Time Limit: 10 Sec Memory Limit: 128 MB[Submit][Status][Discuss]
Description
Bob有一棵n个点的有根树，其中1号点是根节点。Bob在每个点上涂了颜色，并且每个点上的颜色不同。定义一条路径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。Bob可能会进行这几种操作：
1 x:
把点x到根节点的路径上所有的点染上一种没有用过的新颜色。
2 x y:
求x到y的路径的权值。
3 x:
在以x为根的子树中选择一个点，使得这个点到根节点的路径权值最大，求最大权值。
Bob一共会进行m次操作
Input
第一行两个数n,m。
接下来n-1行，每行两个数a,b，表示a与b之间有一条边。
接下来m行，表示操作，格式见题目描述。
Output
每当出现2,3操作，输出一行。
如果是2操作，输出一个数表示路径的权值
如果是3操作，输出一个数表示权值的最大值
Sample Input
5 6
1 2
2 3
3 4
3 5
2 4 5
3 3
1 4
2 4 5
1 5
2 4 5
1 2
2 3
3 4
3 5
2 4 5
3 3
1 4
2 4 5
1 5
2 4 5
Sample Output
3
4
2
2
4
2
2
HINT
1<=n,m<=100000
Source
我们将边两端的点颜色相同的边设为实边，不同的设为虚边。那么一次新增颜色的操作显然就是LCT的access操作！access的时候恰是虚边和实边的转换。
那么我们只要用线段树维护每个点到根的贡献，结合dfs序来实现子树加，每次在LCT进行access的时候进行+-1修改，然后询问的时候用区间求和，区间最值求得答案即可。
Code
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 using namespace std; 9 typedef long long s64; 10 11 const int ONE = 2e5+5; 12 13 int n,m; 14 int x,y,P; 15 int POS[ONE],POSCNT; 16 int pos[ONE],dfn_cnt,size[ONE],dfn[ONE]; 17 int Dep[ONE],son[ONE],Top[ONE]; 18 int lc[ONE],rc[ONE],fa[ONE],fat[ONE]; 19 int res_max,res_value; 20 21 inline int get() 22 { 23 int res=1,Q=1; char c; 24 while( (c=getchar())<48 || c>57) 25 if(c==‘-‘)Q=-1; 26 if(Q) res=c-48; 27 while((c=getchar())>=48 && c<=57) 28 res=res*10+c-48; 29 return res*Q; 30 } 31 32 namespace tree 33 { 34 int next[ONE],first[ONE],go[ONE],tot=0; 35 36 void Add(int u,int v) 37 { 38 next[++tot]=first[u]; first[u]=tot; go[tot]=v; 39 next[++tot]=first[v]; first[v]=tot; go[tot]=u; 40 } 41 42 void Dfs(int u,int father) 43 { 44 pos[u] = ++dfn_cnt; dfn[dfn_cnt] = u; 45 size[u] = 1; 46 Dep[u] = Dep[father] + 1; 47 for(int e=first[u];e;e=next[e]) 48 { 49 int v=go[e]; 50 if(v==father) continue; 51 fa[v] = u; fat[v] = u; 52 Dfs(v,u); 53 size[u] += size[v]; 54 if(size[v] > size[son[u]]) son[u] = v; 55 } 56 } 57 58 void Dfs_twice(int u,int father) 59 { 60 POS[u] = ++POSCNT; 61 if(son[u]) 62 { 63 int v=son[u]; 64 Top[v] = Top[u]; 65 Dfs_twice(v,u); 66 } 67 68 for(int e=first[u];e;e=next[e]) 69 { 70 int v=go[e]; 71 if(v==father || v==son[u]) continue; 72 Top[v] = v; 73 Dfs_twice(v,u); 74 } 75 } 76 77 int LCA(int x,int y) 78 { 79 while(Top[x]!=Top[y]) 80 { 81 if( Dep[Top[x]] < Dep[Top[y]] ) swap(x,y); 82 x = fat[Top[x]]; 83 } 84 if(POS[x] > POS[y]) swap(x,y); 85 return x; 86 } 87 } 88 89 namespace Seg 90 { 91 struct power 92 { 93 int add,value; 94 int maxx; 95 }Node[ONE*4]; 96 97 void pushdown(int i,int Q) 98 { 99 if(Node[i].add)100 {101 Node[i<<1].add += Node[i].add;102 Node[i<<1|1].add += Node[i].add;103 Node[i<<1].maxx += Node[i].add;104 Node[i<<1|1].maxx += Node[i].add; 105 Node[i<<1].value += Node[i].add * (Q-Q/2);106 Node[i<<1|1].value += Node[i].add * (Q/2);107 Node[i].add = 0;108 }109 }110 111 void Build(int i,int l,int r)112 {113 if(l==r)114 {115 Node[i].value =http://www.mamicode.com/ Dep[dfn[l]];116 Node[i].maxx = Dep[dfn[l]];117 return ;118 }119 int mid = l+r>>1;120 Build(i<<1,l,mid); Build(i<<1|1,mid+1,r);121 Node[i].value = http://www.mamicode.com/Node[i<<1].value + Node[i<<1|1].value;122 Node[i].maxx = max(Node[i<<1].maxx, Node[i<<1|1].maxx);123 }124 125 void Update(int i,int l,int r,int L,int R,int x)126 {127 if(L<=l && r<=R)128 {129 Node[i].add += x;130 Node[i].value += (r-l+1)*x;131 Node[i].maxx += x;132 return;133 }134 pushdown(i,r-l+1);135 int mid = l+r>>1;136 if(L<=mid) Update(i<<1,l,mid,L,R,x);137 if(mid+1<=R) Update(i<<1|1,mid+1,r,L,R,x);138 139 Node[i].value = http://www.mamicode.com/Node[i<<1].value + Node[i<<1|1].value;140 Node[i].maxx = max(Node[i<<1].maxx , Node[i<<1|1].maxx);141 }142 143 void Query(int i,int l,int r,int L,int R)144 {145 if(L<=l && r<=R)146 {147 res_max = max(res_max,Node[i].maxx);148 res_value += Node[i].value;149 return;150 }151 pushdown(i,r-l+1);152 int mid = l+r>>1;153 if(L<=mid) Query(i<<1,l,mid,L,R);154 if(mid+1<=R) Query(i<<1|1,mid+1,r,L,R);155 }156 }157 158 namespace LCT159 {160 int is_real(int x)161 {162 return (lc[fa[x]]==x || rc[fa[x]]==x);163 }164 165 void Turn(int x)166 {167 int y = fa[x], z = fa[y];168 int b = x==lc[y] ? rc[x]:lc[x];169 170 fa[x] = z; fa[y] = x;171 if(b) fa[b] = y;172 173 if(z)174 {175 if(y == lc[z]) lc[z] = x;176 else177 if(y == rc[z]) rc[z] = x;178 }179 180 if(x==lc[y]) rc[x]=y,lc[y]=b;181 else lc[x]=y,rc[y]=b;182 }183 184 void Splay(int x)185 {186 while(is_real(x))187 {188 if(is_real(fa[x]))189 {190 if( (lc[fa[x]]==x) == (lc[fa[fa[x]]]==fa[x])) Turn(fa[x]);191 else Turn(x); 192 }193 Turn(x);194 }195 }196 197 int find_root(int x)198 {199 while(lc[x]) x=lc[x];200 return x;201 }202 203 void access(int x)204 {205 for(int p=x,q=0; p; q=p,p=fa[p])206 {207 Splay(p);208 if(rc[p])209 {210 int N = find_root(rc[p]);211 Seg::Update(1,1,n,pos[N],pos[N]+size[N]-1,1);212 }213 214 rc[p] = q;215 if(rc[p])216 {217 int N = find_root(rc[p]);218 Seg::Update(1,1,n,pos[N],pos[N]+size[N]-1,-1);219 }220 }221 }222 }223 224 int Getsum(int x,int y)225 {226 int Ans, Sx, Sy, SLCA, LCA;227 LCA = tree::LCA(x,y);228 x=pos[x], y=pos[y], LCA=pos[LCA];229 res_value = http://www.mamicode.com/0; Seg::Query(1,1,n,x,x); Sx = res_value;230 res_value = http://www.mamicode.com/0; Seg::Query(1,1,n,y,y); Sy = res_value;231 res_value = http://www.mamicode.com/0; Seg::Query(1,1,n,LCA,LCA); SLCA = res_value;232 return Sx+Sy-2*SLCA+1;233 }234 235 int Getmax(int x)236 {237 res_max = 0;238 Seg::Query(1,1,n,pos[x],pos[x]+size[x]-1);239 return res_max;240 }241 242 int main()243 {244 n=get(); m=get();245 for(int i=1;i<=n-1;i++)246 {247 x=get(); y=get();248 tree::Add(x,y);249 }250 251 tree::Dfs(1,0);252 Top[1] = 1, tree::Dfs_twice(1,0);253 Seg::Build(1,1,n);254 255 while(m--)256 {257 P = get(); x=get();258 if(P==1)259 LCT::access(x);260 if(P==2)261 y=get(), printf("%d\n",Getsum(x,y));262 if(P==3)263 printf("%d\n",Getmax(x)); 264 }265 }
【BZOJ4817】【SDOI2017】树点涂色 [LCT][线段树]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。