2243: [SDOI2011]染色
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 3113 Solved: 1204
[Submit][Status][Discuss]
Description
给定一棵有n个节点的无根树和m个操作，操作有2类：
1、将节点a到节点b路径上所有点都染成颜色c；
2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。
Input
第一行包含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）路径上的颜色段数量。
Output
对于每个询问操作，输出一行答案。
Sample Input
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
Sample Output
3
1
2
HINT
数N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。
Source
题解：又是一个树链剖分= =，其实越来越感觉链剖更多的是一种思想，通过树链剖分将树上的区间维护问题转化为线段树维护问题，比如这题就可以转化为一个区间覆盖与区间段数查询问题，关键在于合并区间信息
然后说些要注意的地方：1.在求出LCA再求出两条分链信息之后，记得要倒转过来，否则合并将得不到想要的（注意：区间合并具有方向性）
2.事实上，求出两条支链后不需要把交点，也就是LCA点非要排除掉（HansBug：事实上保留也根本不影响结果，想想为什么= =）
（PS：发现链剖问题每次最终坑我的都是线段树部分啊有木有TT）
/**************************************************************
Problem:
User: HansBug
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/ type
color=record
lef,rig,mid:longint;
end;
point=^node;
node=record
g:longint;
next:point;
end;
var
d:array[..] of color;
a:array[..] of point;
e,len,son,num,anum,top,siz,f:array[..] of longint;
c:array[..,..] of longint;
i,j,k,l,m,n,tot,root:longint;ch:char;
function min(x,y:longint):longint;
begin
if x<y then min:=x else min:=y;
end;
function max(x,y:longint):longint;
begin
if x>y then max:=x else max:=y;
end;
procedure swap(var x,y:longint);
var z:longint;
begin
z:=x;x:=y;y:=z;
end;
function turn(x:color):color;
begin
swap(x.lef,x.rig);
exit(x);
end;
function pure(x:color):boolean;
begin
exit((x.lef=x.rig) and (x.mid=));
end;
function number(x:color):longint;
begin
if x.mid> then exit(x.mid+) else
if x.lef=x.rig then exit() else exit();
end;
function empty(x:color):boolean;
begin
exit((x.lef=-) and (x.rig=-) and (x.mid=))
end;
function getcolor(x,y,z:longint):color;
var p:color;
begin
p.lef:=x;p.rig:=y;p.mid:=z;
exit(p);
end;
function merge(x,y:color):color;
var z:color;
begin
if empty(x) then exit(y);
if empty(y) then exit(x);
z:=getcolor(x.lef,y.rig,);
if not(pure(x)) then inc(z.mid,x.mid+);
if not(pure(y)) then inc(z.mid,y.mid+);
if (z.mid>) and (x.rig=y.lef) then dec(z.mid);
exit(z);
end;
procedure add(x,y:longint);
var p:point;
begin
new(p);p^.g:=y;p^.next:=a[x];a[x]:=p;
end;
procedure dfs(y,x:longint);
var p:point;
begin
len[x]:=len[y]+;
c[,x]:=y;son[x]:=;
siz[x]:=;p:=a[x];
while p<>nil do
begin
if p^.g<>y then
begin
dfs(x,p^.g);
if (son[x]=) or (siz[p^.g]>siz[son[x]]) then son[x]:=p^.g;
inc(siz[x],siz[p^.g]);
end;
p:=p^.next;
end;
end;
procedure dfs2(y,x,z:longint);
var p:point;
begin
top[x]:=z;inc(tot);num[x]:=tot;anum[tot]:=x;
if son[x]<> then dfs2(x,son[x],z);
p:=a[x];
while p<>nil do
begin
if (p^.g<>y) and (p^.g<>son[x]) then dfs2(x,p^.g,p^.g);
p:=p^.next;
end;
end;
procedure built(z,x,y:longint);
begin
if x=y then
d[z]:=getcolor(f[anum[x]],f[anum[x]],)
else
begin
built(z*,x,(x+y) div );
built(z*+,(x+y) div +,y);
d[z]:=merge(d[z*],d[z*+]);
end;
e[z]:=-;
end;
procedure ext(z,x,y:longint);
begin
if e[z]=- then exit;
d[z]:=getcolor(e[z],e[z],);
if x<>y then
begin
e[z*]:=e[z];
e[z*+]:=e[z];
end;
e[z]:=-;
end;
function cover(z,x,y,l,r,t:longint):color;
var p1,p2:color;
begin
if l>r then if e[z]<>- then exit(getcolor(e[z],e[z],)) else exit(d[z]);
if (l=x) and (r=y) then
begin
e[z]:=t;
exit(getcolor(t,t,));
end;
ext(z,x,y);
p1:=cover(z*,x,(x+y) div ,l,min(r,(x+y) div ),t);
p2:=cover(z*+,(x+y) div +,y,max((x+y) div +,l),r,t);
d[z]:=merge(p1,p2);
exit(d[z]);
end;
function doit(z,x,y,l,r:longint):color;
var p1,p2:color;
begin
if l>r then exit(getcolor(-,-,));
if e[z]<>- then exit(getcolor(e[z],e[z],));
if (x=l) and (y=r) then exit(d[z]);
p1:=doit(z*,x,(x+y) div ,l,min(r,(x+y) div ));
p2:=doit(z*+,(x+y) div +,y,max((x+y) div +,l),r);
exit(merge(p1,p2));
end;
function getup(x,y:longint):longint;
var i:longint;
begin
i:=;
while y> do
begin
if odd(y) then x:=c[i,x];
inc(i);y:=y div ;
end;
exit(x);
end;
function getcom(x,y:longint):longint;
var i:longint;
begin
if len[x]<len[y] then swap(x,y);
x:=getup(x,len[x]-len[y]);
if x=y then exit(x);
for i:=trunc(round(ln(len[x])/ln())) downto do
if c[i,x]<>c[i,y] then
begin
x:=c[i,x];
y:=c[i,y];
end;
exit(c[,x]);
end;
procedure treecolor(x,y,t:longint);
var z,i:longint;
begin
z:=getcom(x,y);
repeat
if len[top[x]]<len[z] then i:=z else i:=top[x];
cover(,,n,num[i],num[x],t);
if i=z then break;
x:=c[,i];
until false;
repeat
if len[top[y]]<len[z] then i:=z else i:=top[y];
cover(,,n,num[i],num[y],t);
if i=z then break;
y:=c[,i];
until false;
end;
function treecount(x,y:longint):longint;
var z,i:longint;p1,p2:color;
begin
p1:=getcolor(-,-,);p2:=getcolor(-,-,);
z:=getcom(x,y);
repeat
if len[top[x]]<len[z] then i:=z else i:=top[x];
p1:=merge(p1,turn(doit(,,n,num[i],num[x])));
if i=z then break;
x:=c[,i];
until false; repeat
if len[top[y]]<len[z] then i:=z else i:=top[y];
p2:=merge(doit(,,n,num[i],num[y]),p2);
if i=z then break;
y:=c[,i];
until false; exit(number(merge(p1,p2)));
end;
begin
readln(n,m);
for i:= to n do a[i]:=nil;
for i:= to n do read(f[i]);
readln;
for i:= to n- do
begin
readln(j,k);
add(j,k);add(k,j);
end;
root:=;dfs(,root);dfs2(,root,root);
for i:= to trunc(round(ln(n)/ln()))+ do
for j:= to n do
c[i,j]:=c[i-,c[i-,j]];
built(,,n); for i:= to m do
begin
read(ch);
case ch of
'Q':begin
readln(j,k);
writeln(treecount(j,k));
end;
'C':begin
readln(j,k,l);
treecolor(j,k,l);
end;
end;
end;
readln;
end.