題意：
給定一棵有n個節點的樹和m個操作，操作有：
C a b c 將樹上a到b路徑上所有點都染成顏色c；
Q a b 詢問樹上a到b路徑上的顏色段數量（連續相同顏色是同一段）
思路：
樹上的路徑！樹鏈剖分！
可惜智障了…沒想到怎麼維護顏色段【媽的這麼簡單的維護當時居然不會
樹剖劃分一下樹，然後線段樹維護每一段的最左lc[]最右rc[]和不同顏色色段數量和sum[]，查詢的時候關於判斷樹中被切開的段的左右端是否一樣還是需要謹慎，最後我參考了一下黃學長的處理思路來著
最後：顏色可能有0
/**************************************************************
Problem: 2243
User: Rainbow6174
Language: C++
Result: Accepted
Time:9056 ms
Memory:20356 kb
****************************************************************/
#include
#include
#include
#include
#define lson (o<<1)
#define rson ((o<<1)|1)
using namespace std;
const int maxn = 100005;
int n,m,u,v,x,tot;
int c[maxn],fa[maxn],son[maxn],size[maxn],deep[maxn],rt[maxn],in[maxn],fin[maxn];
int lc[maxn*4],rc[maxn*4],sum[maxn*4],lazy[maxn*4];
vector edge[maxn];
char s[5];
void dfs(int x,int pre)
{
fa[x] = pre;
son[x] = -1;
size[x] = 1;
deep[x] = deep[pre]+1;
for(int i = 0; i < edge[x].size(); i++)
if(edge[x][i] != pre)
{
dfs(edge[x][i],x);
size[x] += size[edge[x][i]];
if(son[x]==-1 || size[edge[x][i]]>size[son[x]]) son[x]=edge[x][i];
}
}
void init(int x,int root)
{
rt[x] = root;
in[x] = ++tot;
fin[in[x]] = x;
if(son[x]==-1)return;
init(son[x],root);
for(int i = 0; i < edge[x].size(); i++)
if(edge[x][i] != fa[x] && edge[x][i]!=son[x])
init(edge[x][i],edge[x][i]);
}
void maintain(int o,int l,int r)
{
if(l==r)return;
lc[o]=lc[lson];
rc[o]=rc[rson];
sum[o]=sum[lson]+sum[rson]-(rc[lson]==lc[rson]);
}
void pushdown(int o,int l,int r)
{
if(lazy[o]!=-1 && l!=r)
{
lc[lson]=lc[rson]=lazy[o];
rc[lson]=rc[rson]=lazy[o];
sum[lson]=sum[rson]=1;
lazy[lson]=lazy[rson]=lazy[o];
}
lazy[o]=-1;
}
void buildtree(int o,int l,int r)
{
if(l==r)
{
lc[o]=rc[o]=c[fin[l]];
sum[o]=1;
return;
}
int mid = (l+r)/2;
buildtree(lson,l,mid);
buildtree(rson,mid+1,r);
maintain(o,l,r);
}
void addtree(int o,int l,int r,int L,int R,int c)
{
pushdown(o,l,r);
if(l>R || r=L && r<=R)
{
lazy[o]=c;
lc[o]=rc[o]=c;
sum[o]=1;
return;
}
int mid=(l+r)/2;
addtree(lson,l,mid,L,R,c);
addtree(rson,mid+1,r,L,R,c);
maintain(o,l,r);
}
int getsum(int o,int l,int r,int L,int R)
{
pushdown(o,l,r);
if(l>R || r=L && r<=R) return sum[o];
int mid=(l+r)/2;
int ret1=getsum(lson,l,mid,L,R);
int ret2=getsum(rson,mid+1,r,L,R);
maintain(o,l,r);
if(ret1 && ret2)return ret1+ret2-(rc[lson]==lc[rson]);
else return ret1+ret2;
}
int getcol(int o,int l,int r,int x)
{
pushdown(o,l,r);
if(l>x || r=deep[rt[y]])addtree(1,1,tot,in[rt[x]],in[x],col),x=fa[rt[x]];
else addtree(1,1,tot,in[rt[y]],in[y],col),y=fa[rt[y]];
}
if(deep[x]>=deep[y])addtree(1,1,tot,in[y],in[x],col);
else addtree(1,1,tot,in[x],in[y],col);
}
int query(int x,int y)
{
int ret=0,lxcol=-1,lycol=-1;
while(rt[x]!=rt[y])
{
//cout<
