首页 > 代码库 > 【Foreign】染色 [LCT][线段树]
【Foreign】染色 [LCT][线段树]
染色
Time Limit: 20 Sec Memory Limit: 256 MBDescription
Input
Output
Sample Input
13
0 1
0 2
1 11
1 10
1 9
9 12
2 5
5 8
2 4
2 3
4 6
4 7
7
q 0
O 4
q 6
q 2
O 9
q 9
q 2
0 1
0 2
1 11
1 10
1 9
9 12
2 5
5 8
2 4
2 3
4 6
4 7
7
q 0
O 4
q 6
q 2
O 9
q 9
q 2
Sample Output
2.0000000000
1.0000000000
0.8571428571
0.5000000000
1.8571428571
1.0000000000
0.8571428571
0.5000000000
1.8571428571
HINT
Main idea
询问x到根路径上不同颜色的个数，支持将x到根的路径上的点全部设为新的颜色。
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<ctime> 8 #include<cmath> 9 using namespace std; 10 typedef long long s64; 11 const int ONE=1500001; 12 13 int n,m,x,y; 14 int pos[ONE],size[ONE],Dep[ONE],dfn[ONE],cnt; 15 s64 res; 16 char ch[5]; 17 18 int lc[ONE],rc[ONE],fa[ONE]; 19 20 int get() 21 { 22 int res=1,Q=1;char c; 23 while( (c=getchar())<48 || c>57 ) 24 if(c==‘-‘)Q=-1; 25 res=c-48; 26 while( (c=getchar())>=48 && c<=57 ) 27 res=res*10+c-48; 28 return res*Q; 29 } 30 31 namespace tree 32 { 33 int next[ONE],first[ONE],go[ONE],tot; 34 35 void Add(int u,int v) 36 { 37 next[++tot]=first[u]; first[u]=tot; go[tot]=v; 38 next[++tot]=first[v]; first[v]=tot; go[tot]=u; 39 } 40 41 void Dfs(int u,int father) 42 { 43 pos[u] = ++cnt; dfn[cnt] = u; 44 size[u] = 1; 45 for(int e=first[u];e;e=next[e]) 46 { 47 int v=go[e]; 48 if(v==father) continue; 49 Dep[v] = Dep[u] + 1; 50 fa[v] = u; 51 Dfs(v,u); 52 size[u] += size[v]; 53 } 54 } 55 } 56 57 namespace Seg 58 { 59 struct power 60 { 61 s64 add,value; 62 }Node[ONE]; 63 64 void pushdown(int i,int Q) 65 { 66 if(Node[i].add) 67 { 68 Node[i<<1].add+=Node[i].add; 69 Node[i<<1|1].add+=Node[i].add; 70 Node[i<<1].value+=Node[i].add*(Q-Q/2); 71 Node[i<<1|1].value+=Node[i].add*(Q/2); 72 Node[i].add=0; 73 } 74 } 75 76 void Build(int i,int l,int r) 77 { 78 if(l==r) 79 { 80 Node[i].value =http://www.mamicode.com/ Dep[dfn[l]]; 81 return; 82 } 83 int mid=(l+r)>>1; 84 Build(i<<1,l,mid); Build(i<<1|1,mid+1,r); 85 Node[i].value=http://www.mamicode.com/Node[i<<1].value+Node[i<<1|1].value; 86 } 87 88 void Update(int i,int l,int r,int L,int R,int x) 89 { 90 if(L<=l && r<=R) 91 { 92 Node[i].add+=x; 93 Node[i].value+=(s64)(r-l+1)*x; 94 return; 95 } 96 97 pushdown(i,r-l+1); 98 int mid=(l+r)>>1; 99 if(L<=mid) Update(i<<1,l,mid,L,R,x);100 if(mid+1<=R) Update(i<<1|1,mid+1,r,L,R,x);101 Node[i].value=http://www.mamicode.com/Node[i<<1].value+Node[i<<1|1].value;102 }103 104 void Query(int i,int l,int r,int L,int R)105 {106 if(L<=l && r<=R)107 {108 res+=Node[i].value;109 return;110 }111 pushdown(i,r-l+1);112 int mid=(l+r)>>1;113 if(L<=mid) Query(i<<1,l,mid,L,R);114 if(mid+1<=R) Query(i<<1|1,mid+1,r,L,R);115 } 116 }117 118 namespace LCT119 {120 int is_real(int x)121 {122 return (lc[fa[x]]==x || rc[fa[x]]==x);123 }124 125 void Turn(int x)126 {127 int y=fa[x],z=fa[y];128 int b= x==lc[y] ? rc[x]:lc[x];129 130 fa[x]=z; fa[y]=x;131 if(b) fa[b]=y;132 133 if(z)134 {135 if(y==lc[z]) lc[z]=x;136 else 137 if(y==rc[z]) rc[z]=x;138 }139 140 if(x==lc[y]) rc[x]=y,lc[y]=b;141 else lc[x]=y,rc[y]=b;142 }143 144 void Splay(int x)145 {146 while(is_real(x))147 {148 if(is_real(fa[x]))149 {150 if( (lc[fa[x]]==x) == (lc[fa[fa[x]]]==fa[x]) ) Turn(fa[x]);151 else Turn(x);152 }153 Turn(x);154 }155 }156 157 int find_root(int x)158 {159 while(lc[x]) x=lc[x];160 return x;161 }162 163 void access(int x)164 {165 for(int p=x,q=0; p; q=p,p=fa[p])166 {167 Splay(p);168 if(rc[p])169 {170 int N=find_root(rc[p]);171 Seg::Update(1,1,n,pos[N],pos[N]+size[N]-1,+1);172 } 173 rc[p]=q;174 if(rc[p])175 {176 int N=find_root(rc[p]);177 Seg::Update(1,1,n,pos[N],pos[N]+size[N]-1,-1);178 }179 }180 }181 }182 183 int main()184 {185 n=get();186 for(int i=1;i<n;i++)187 {188 x=get(); y=get();189 x++; y++;190 tree::Add(x,y);191 }192 tree::Dfs(1,0);193 Seg::Build(1,1,n);194 195 m=get();196 while(m--)197 {198 scanf("%s",ch); x=get(); x++;199 if(ch[0]==‘O‘)200 {201 LCT::access(x);202 }203 else204 {205 res=0;206 Seg::Query(1,1,n,pos[x],pos[x]+size[x]-1);207 printf("%.10lf\n",(double)res/size[x]);208 }209 }210 211 }
【Foreign】染色 [LCT][线段树]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。