Description
给定一棵有n个节点的无根树和m个操作，操作有2类：
1、将节点a到节点b路径上所有点都染成颜色c；
2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。
与上一题差别不大，主要就是solve过程要根据左端点和右端点的颜色处理合并时候的情况
线段树的每个节点要记录颜色段数|最左边的颜色|最右边的颜色
同时往下传的时候标记要做好（之前那道题是单点修改所以不用考虑下传
因为这个昨晚调了一个晚上无果...果然是早上头脑清醒的多 一下子就改好了...
program bzoj2243;
const maxn=;maxm=;
var ter,next:array[-..maxm]of longint;
link,pos,deep,size,belong,v:array[-..maxn]of longint;
fa:array[-..maxn,-..]of longint;
cnt,n,m,i,j,x,y,z,t:longint;
ch:char;
tr:array[-..*maxn]of record l,r,lc,rc,cover:longint;wait:boolean;end; procedure add(x,y:longint);
begin
inc(j);ter[j]:=y;next[j]:=link[x];link[x]:=j;
inc(j);ter[j]:=x;next[j]:=link[y];link[y]:=j;
end; procedure dfs1(p:longint);
var i,j:longint;
begin
size[p]:=;
for i:= to do
begin
if deep[p]<= << i then break;
fa[p][i]:=fa[fa[p][i-]][i-];
end;
j:=link[p];
while j<> do
begin
if deep[ter[j]]= then
begin
deep[ter[j]]:=deep[p]+;
fa[ter[j]][]:=p;
dfs1(ter[j]);
inc(size[p],size[ter[j]]);
end;
j:=next[j];
end;
end; procedure dfs2(p,chain:longint);
var j,k:longint;
begin
inc(cnt);pos[p]:=cnt;belong[p]:=chain;
k:=;
j:=link[p];
while j<> do
begin
if deep[ter[j]]>deep[p] then
if size[ter[j]]>size[k] then k:=ter[j];
j:=next[j];
end;
if k= then exit;
dfs2(k,chain);
j:=link[p];
while j<> do
begin
if (deep[ter[j]]>deep[p])and(k<>ter[j]) then dfs2(ter[j],ter[j]);
j:=next[j];
end;
end; procedure build(p,l,r:longint);
var mid:longint;
begin
tr[p].l:=l;tr[p].r:=r;tr[p].cover:=;tr[p].lc:=-;tr[p].rc:=-;
if l=r then exit;
mid:=(l+r) >> ;
build(p << ,l,mid);
build(p << +,mid+,r);
end; procedure insert(p,l,r,x:longint);
var mid:longint;
begin
if (tr[p].l=l)and(tr[p].r=r) then
begin
tr[p].cover:=;tr[p].lc:=x;tr[p].rc:=x;tr[p].wait:=true;
exit;
end;
mid:=(tr[p].l+tr[p].r) >> ;
if tr[p].wait then
begin
tr[p << ].cover:=;tr[p << ].lc:=tr[p].lc;tr[p << ].rc:=tr[p].rc;
tr[p << +].cover:=;tr[p << +].lc:=tr[p].lc;tr[p << +].rc:=tr[p].rc;
tr[p].wait:=false;
tr[p << ].wait:=true;tr[p << +].wait:=true;
end;
if r<=mid then insert(p << ,l,r,x) else
if l>mid then insert(p << +,l,r,x) else
begin
insert(p << ,l,mid,x);
insert(p << +,mid+,r,x);
end;
tr[p].cover:=tr[p << ].cover+tr[p << +].cover;
if tr[p << ].rc=tr[p << +].lc then dec(tr[p].cover);
tr[p].lc:=tr[p << ].lc;tr[p].rc:=tr[p << +].rc;
end; function lca(x,y:longint):longint;
var tem,i:longint;
begin
if deep[x]<deep[y] then
begin
tem:=x;x:=y;y:=tem;
end;
if deep[x]>deep[y] then
begin
i:=trunc(ln(deep[x]-deep[y])/ln());
while deep[x]<>deep[y] do
begin
while (deep[x]-deep[y]>= << i) do x:=fa[x][i];
dec(i);
end;
end;
if x=y then exit(x);
i:=trunc(ln(n)/ln());
while fa[x][]<>fa[y][] do
begin
while (fa[x][i]<>fa[y][i]) do
begin
x:=fa[x,i];y:=fa[y][i];
end;
dec(i);
end;
exit(fa[x,]);
end; procedure query(p,l,r:longint;var lc,rc,ave:longint);
var mid,ll,rr,x,tem:longint;
begin
if (tr[p].l=l)and(tr[p].r=r) then
begin
lc:=tr[p].lc;rc:=tr[p].rc;
ave:=tr[p].cover;
exit;
end;
mid:=(tr[p].l+tr[p].r) >> ;
if tr[p].wait then
begin
tr[p << ].cover:=;tr[p << ].lc:=tr[p].lc;tr[p << ].rc:=tr[p].rc;
tr[p << +].cover:=;tr[p << +].lc:=tr[p].lc;tr[p << +].rc:=tr[p].rc;
tr[p].wait:=false;
tr[p << ].wait:=true;tr[p << +].wait:=true;
end;
if r<=mid then query(p << ,l,r,lc,rc,ave) else
if l>mid then query(p << +,l,r,lc,rc,ave) else
begin
query(p << ,l,mid,lc,ll,ave);
query(p << +,mid+,r,rr,rc,tem);
inc(ave,tem);
if ll=rr then dec(ave);
end;
end; function solve(x,y:longint):longint;
var r,sum,lc,rc,tem:longint;
begin
r:=-;sum:=;
while belong[x]<>belong[y] do
begin
query(,pos[belong[x]],pos[x],lc,rc,tem);
inc(sum,tem);
if rc=r then dec(sum);
r:=lc;
x:=fa[belong[x]][];
end;
query(,pos[y],pos[x],lc,rc,tem);
inc(sum,tem);
if rc=r then dec(sum);
exit(sum);
end; procedure mend(x,y,z:longint);
begin
while belong[x]<>belong[y] do
begin
insert(,pos[belong[x]],pos[x],z);
x:=fa[belong[x]][];
end;
insert(,pos[y],pos[x],z);
end; begin
readln(n,m);
for i:= to n do read(v[i]);readln;
j:=;
for i:= to n- do
begin
readln(x,y);
add(x,y);
end;
deep[]:=;
dfs1();
cnt:=;dfs2(,);
build(,,n);
for i:= to n do insert(,pos[i],pos[i],v[i]);
for i:= to m do
begin
read(ch);
if ch='C' then
begin
readln(x,y,z);
t:=lca(x,y);
mend(x,t,z);mend(y,t,z);
end else
begin
readln(x,y);
z:=lca(x,y);
writeln(solve(x,z)+solve(y,z)-);
end;
end;
end.
[UPD.5.11]今天复习树链剖分，挑了这道题写了写。一个地方WA检查了三遍对拍了一个多小时才找出来...
就是在判断链之间答案合并的时候是从右往左的而不是从左往右...习惯性的写法干脆检查的时候都忽略了这一点...
另外这次用C++大概150行左右..感觉还不错
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#define maxn 1000010
#define maxm 2000010
struct node{
int l,r,lc,rc,count,wait;
}tr[maxn*];
int next[maxm],ter[maxm],link[maxn],pos[maxn],belong[maxn],dep[maxn];
int fa[maxn][],sz[maxn],n,m,e,v[maxn],cnt;
char ch[];
void swap(int &x,int &y){
int tmp=x;x=y;y=tmp;
}
void add(int x,int y){
ter[++e]=y;next[e]=link[x];link[x]=e;
ter[++e]=x;next[e]=link[y];link[y]=e;
}
void dfs1(int p){
sz[p]=;
for (int i=;i<=&&dep[p]>(<<i);i++) fa[p][i]=fa[fa[p][i-]][i-];
for (int i=link[p];i;i=next[i]) if (dep[ter[i]]==){
dep[ter[i]]=dep[p]+;
fa[ter[i]][]=p;
dfs1(ter[i]);
sz[p]+=sz[ter[i]];
}
}
void dfs2(int p,int chain){
pos[p]=++cnt;belong[p]=chain;
int k=;
for (int i=link[p];i;i=next[i]) if (dep[ter[i]]==dep[p]+&&sz[ter[i]]>sz[k]) k=ter[i];
if (k==) return;
dfs2(k,chain);
for (int i=link[p];i;i=next[i]) if (dep[ter[i]]==dep[p]+&&ter[i]!=k) dfs2(ter[i],ter[i]);
}
void update(int p){
tr[p].lc=tr[p<<].lc;
tr[p].rc=tr[(p<<)+].rc;
tr[p].count=tr[p<<].count+tr[(p<<)+].count;
if (tr[p<<].rc==tr[(p<<)+].lc) tr[p].count--;
}
void push(int p){
if (tr[p].wait==-) return;
int u=p<<,w=(p<<)+,col=tr[p].wait;
tr[u].lc=tr[u].rc=tr[u].wait=col;tr[u].count=;
tr[w].lc=tr[w].rc=tr[w].wait=col;tr[w].count=;
tr[p].wait=-;
}
void build(int p,int l,int r){
tr[p].l=l;tr[p].r=r;tr[p].wait=-;
if (l==r) return;
int mid=(l+r) >> ;
build(p<<,l,mid);build((p<<)+,mid+,r);
}
int lca(int x,int y){
if (dep[x]<dep[y]) swap(x,y);
int i;
if (dep[x]>dep[y]){
i=(int)(log(dep[x]-dep[y])/log());
while (dep[x]>dep[y]){
while (dep[x]-dep[y]>=<<i) x=fa[x][i];
i--;
}
}
if (x==y) return x;
i=(int)(log(n)/log());
while (fa[x][]!=fa[y][]){
while (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
i--;
}
return fa[x][];
}
void insert(int p,int l,int r,int col){
if (tr[p].l==l&&tr[p].r==r){
tr[p].lc=col;tr[p].rc=col;tr[p].wait=col;tr[p].count=;
return;
}
push(p);
int mid=(tr[p].l+tr[p].r)>>;
if (r<=mid) insert(p<<,l,r,col);else
if (l>mid) insert((p<<)+,l,r,col);else{
insert(p<<,l,mid,col);insert((p<<)+,mid+,r,col);
}
update(p);
}
void query(int p,int l,int r,int &lc,int &rc,int &ans){
if (tr[p].l==l&&tr[p].r==r){
lc=tr[p].lc;rc=tr[p].rc;ans=tr[p].count;
return;
}
push(p);
int mid=(tr[p].l+tr[p].r)>>;
if (r<=mid) query(p<<,l,r,lc,rc,ans);else
if (l>mid) query((p<<)+,l,r,lc,rc,ans);else
{
int ll,rr,ans1;
query(p<<,l,mid,lc,rr,ans);
query((p<<)+,mid+,r,ll,rc,ans1);
ans+=ans1;if (ll==rr) ans--;
}
update(p);
}
void change(int x,int y,int col){
while (belong[x]!=belong[y]){
insert(,pos[belong[x]],pos[x],col);
x=fa[belong[x]][];
}
insert(,pos[y],pos[x],col);
}
int solve(int x,int y){
int sum=,r=-,ll,rr,tmp;
while (belong[x]!=belong[y]){
query(,pos[belong[x]],pos[x],ll,rr,tmp);
x=fa[belong[x]][];
sum+=tmp;if (rr==r) sum--;
r=ll;
}
query(,pos[y],pos[x],ll,rr,tmp);
sum+=tmp;if (rr==r) sum--;
return sum;
}
int main(){
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++) scanf("%d",&v[i]);
e=;
int x,y,col,t;
for (int i=;i<=n-;i++) scanf("%d%d",&x,&y),add(x,y);
dep[]=;dfs1();
cnt=;dfs2(,);
build(,,n);
for (int i=;i<=n;i++) insert(,pos[i],pos[i],v[i]);
for (int i=;i<=m;i++){
scanf("%s",ch);
if (ch[]=='C'){
scanf("%d%d%d",&x,&y,&col);
t=lca(x,y);
change(x,t,col);change(y,t,col);
}else{
scanf("%d%d",&x,&y);
t=lca(x,y);
printf("%d\n",solve(x,t)+solve(y,t)-);
}
}
return ;
}