Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 3113 Solved: 1204
给定一棵有n个节点的无根树和m个操作,操作有2类:
1、将节点a到节点b路径上所有点都染成颜色c;
2、询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),如“112221”由3段组成:“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。
第一行包含2个整数n和m,分别表示节点数和操作数;
第二行包含n个正整数表示n个节点的初始颜色
下面 行每行包含两个整数x和y,表示x和y之间有一条无向边。
下面 行每行描述一个操作:
“C a b c”表示这是一个染色操作,把节点a到节点b路径上所有点(包括a和b)都染成颜色c;
“Q a b”表示这是一个询问操作,询问节点a到节点b(包括a和b)路径上的颜色段数量。
对于每个询问操作,输出一行答案。
6 5 2 2 1 2 1 1 1 2 1 3 2 4 2 5 2 6 Q 3 5 C 2 1 1 Q 3 5 C 5 1 2 Q 3 5
3 1 2
数N<=10^5,操作数M<=10^5,所有的颜色C为整数且在[0, 10^9]之间。
题解:又是一个树链剖分= =,其实越来越感觉链剖更多的是一种思想,通过树链剖分将树上的区间维护问题转化为线段树维护问题,比如这题就可以转化为一个区间覆盖与区间段数查询问题,关键在于合并区间信息
然后说些要注意的地方:1.在求出LCA再求出两条分链信息之后,记得要倒转过来,否则合并将得不到想要的(注意:区间合并具有方向性)
2.事实上,求出两条支链后不需要把交点,也就是LCA点非要排除掉(HansBug:事实上保留也根本不影响结果,想想为什么= =)
(PS:发现链剖问题每次最终坑我的都是线段树部分啊有木有TT)
1 /**************************************************************
2 Problem: 2243
3 User: HansBug
4 Language: Pascal
5 Result: Accepted
6 Time:14940 ms
7 Memory:55812 kb
8 ****************************************************************/
9
10 type
11 color=record
12 lef,rig,mid:longint;
13 end;
14 point=^node;
15 node=record
16 g:longint;
17 next:point;
18 end;
19 var
20 d:array[0..1000005] of color;
21 a:array[0..100005] of point;
22 e,len,son,num,anum,top,siz,f:array[0..1000005] of longint;
23 c:array[0..20,0..100005] of longint;
24 i,j,k,l,m,n,tot,root:longint;ch:char;
25 function min(x,y:longint):longint;
26 begin
27 if x<y then min:=x else min:=y;
28 end;
29 function max(x,y:longint):longint;
30 begin
31 if x>y then max:=x else max:=y;
32 end;
33 procedure swap(var x,y:longint);
34 var z:longint;
35 begin
36 z:=x;x:=y;y:=z;
37 end;
38 function turn(x:color):color;
39 begin
40 swap(x.lef,x.rig);
41 exit(x);
42 end;
43 function pure(x:color):boolean;
44 begin
45 exit((x.lef=x.rig) and (x.mid=0));
46 end;
47 function number(x:color):longint;
48 begin
49 if x.mid>0 then exit(x.mid+2) else
50 if x.lef=x.rig then exit(1) else exit(2);
51 end;
52 function empty(x:color):boolean;
53 begin
54 exit((x.lef=-1) and (x.rig=-1) and (x.mid=0))
55 end;
56 function getcolor(x,y,z:longint):color;
57 var p:color;
58 begin
59 p.lef:=x;p.rig:=y;p.mid:=z;
60 exit(p);
61 end;
62 function merge(x,y:color):color;
63 var z:color;
64 begin
65 if empty(x) then exit(y);
66 if empty(y) then exit(x);
67 z:=getcolor(x.lef,y.rig,0);
68 if not(pure(x)) then inc(z.mid,x.mid+1);
69 if not(pure(y)) then inc(z.mid,y.mid+1);
70 if (z.mid>0) and (x.rig=y.lef) then dec(z.mid);
71 exit(z);
72 end;
73 procedure add(x,y:longint);
74 var p:point;
75 begin
76 new(p);p^.g:=y;p^.next:=a[x];a[x]:=p;
77 end;
78 procedure dfs(y,x:longint);
79 var p:point;
80 begin
81 len[x]:=len[y]+1;
82 c[0,x]:=y;son[x]:=0;
83 siz[x]:=1;p:=a[x];
84 while p<>nil do
85 begin
86 if p^.g<>y then
87 begin
88 dfs(x,p^.g);
89 if (son[x]=0) or (siz[p^.g]>siz[son[x]]) then son[x]:=p^.g;
90 inc(siz[x],siz[p^.g]);
91 end;
92 p:=p^.next;
93 end;
94 end;
95 procedure dfs2(y,x,z:longint);
96 var p:point;
97 begin
98 top[x]:=z;inc(tot);num[x]:=tot;anum[tot]:=x;
99 if son[x]<>0 then dfs2(x,son[x],z);
100 p:=a[x];
101 while p<>nil do
102 begin
103 if (p^.g<>y) and (p^.g<>son[x]) then dfs2(x,p^.g,p^.g);
104 p:=p^.next;
105 end;
106 end;
107 procedure built(z,x,y:longint);
108 begin
109 if x=y then
110 d[z]:=getcolor(f[anum[x]],f[anum[x]],0)
111 else
112 begin
113 built(z*2,x,(x+y) div 2);
114 built(z*2+1,(x+y) div 2+1,y);
115 d[z]:=merge(d[z*2],d[z*2+1]);
116 end;
117 e[z]:=-1;
118 end;
119 procedure ext(z,x,y:longint);
120 begin
121 if e[z]=-1 then exit;
122 d[z]:=getcolor(e[z],e[z],0);
123 if x<>y then
124 begin
125 e[z*2]:=e[z];
126 e[z*2+1]:=e[z];
127 end;
128 e[z]:=-1;
129 end;
130 function cover(z,x,y,l,r,t:longint):color;
131 var p1,p2:color;
132 begin
133 if l>r then if e[z]<>-1 then exit(getcolor(e[z],e[z],0)) else exit(d[z]);
134 if (l=x) and (r=y) then
135 begin
136 e[z]:=t;
137 exit(getcolor(t,t,0));
138 end;
139 ext(z,x,y);
140 p1:=cover(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2),t);
141 p2:=cover(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r,t);
142 d[z]:=merge(p1,p2);
143 exit(d[z]);
144 end;
145 function doit(z,x,y,l,r:longint):color;
146 var p1,p2:color;
147 begin
148 if l>r then exit(getcolor(-1,-1,0));
149 if e[z]<>-1 then exit(getcolor(e[z],e[z],0));
150 if (x=l) and (y=r) then exit(d[z]);
151 p1:=doit(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2));
152 p2:=doit(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r);
153 exit(merge(p1,p2));
154 end;
155 function getup(x,y:longint):longint;
156 var i:longint;
157 begin
158 i:=0;
159 while y>0 do
160 begin
161 if odd(y) then x:=c[i,x];
162 inc(i);y:=y div 2;
163 end;
164 exit(x);
165 end;
166 function getcom(x,y:longint):longint;
167 var i:longint;
168 begin
169 if len[x]<len[y] then swap(x,y);
170 x:=getup(x,len[x]-len[y]);
171 if x=y then exit(x);
172 for i:=trunc(round(ln(len[x])/ln(2))) downto 0 do
173 if c[i,x]<>c[i,y] then
174 begin
175 x:=c[i,x];
176 y:=c[i,y];
177 end;
178 exit(c[0,x]);
179 end;
180 procedure treecolor(x,y,t:longint);
181 var z,i:longint;
182 begin
183 z:=getcom(x,y);
184 repeat
185 if len[top[x]]<len[z] then i:=z else i:=top[x];
186 cover(1,1,n,num[i],num[x],t);
187 if i=z then break;
188 x:=c[0,i];
189 until false;
190 repeat
191 if len[top[y]]<len[z] then i:=z else i:=top[y];
192 cover(1,1,n,num[i],num[y],t);
193 if i=z then break;
194 y:=c[0,i];
195 until false;
196 end;
197 function treecount(x,y:longint):longint;
198 var z,i:longint;p1,p2:color;
199 begin
200 p1:=getcolor(-1,-1,0);p2:=getcolor(-1,-1,0);
201 z:=getcom(x,y);
202 repeat
203 if len[top[x]]<len[z] then i:=z else i:=top[x];
204 p1:=merge(p1,turn(doit(1,1,n,num[i],num[x])));
205 if i=z then break;
206 x:=c[0,i];
207 until false;
208
209 repeat
210 if len[top[y]]<len[z] then i:=z else i:=top[y];
211 p2:=merge(doit(1,1,n,num[i],num[y]),p2);
212 if i=z then break;
213 y:=c[0,i];
214 until false;
215
216 exit(number(merge(p1,p2)));
217 end;
218 begin
219 readln(n,m);
220 for i:=1 to n do a[i]:=nil;
221 for i:=1 to n do read(f[i]);
222 readln;
223 for i:=1 to n-1 do
224 begin
225 readln(j,k);
226 add(j,k);add(k,j);
227 end;
228 root:=1;dfs(0,root);dfs2(0,root,root);
229 for i:=1 to trunc(round(ln(n)/ln(2)))+1 do
230 for j:=1 to n do
231 c[i,j]:=c[i-1,c[i-1,j]];
232 built(1,1,n);
233
234 for i:=1 to m do
235 begin
236 read(ch);
237 case ch of
238 'Q':begin
239 readln(j,k);
240 writeln(treecount(j,k));
241 end;
242 'C':begin
243 readln(j,k,l);
244 treecolor(j,k,l);
245 end;
246 end;
247 end;
248 readln;
249 end.