P2486 [SDOI2011]染色 WA了，只有35

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>

using namespace std;

struct bian
{
	int v,nex;
}side[900000];
struct nodee
{
	int l,r,lc,rc,summ,add;
}tre[900000];
struct node
{
	int pos,head,f,dep,size,son,top,c;
}p[900000];

int c[900000],n,m,len=0;

inline void xiachuan(int w)
{
	if(tre[w].add==-1)return;
	tre[w*2].lc=tre[w].add;tre[w*2].rc=tre[w].add;
	tre[w*2+1].lc=tre[w].add;tre[w*2+1].rc=tre[w].add;
	tre[w*2].add=tre[w].add;tre[w*2+1].add=tre[w].add;
	tre[w*2].summ=1;tre[w*2+1].summ=1;
	tre[w].add=-1;
}

void build(int w,int l,int r)
{
	tre[w].l=l;tre[w].r=r;tre[w].add=-1;
	if(tre[w].l==tre[w].r){tre[w].summ=1;tre[w].lc=c[l];tre[w].rc=c[l];return;}
	build(w*2,l,(l+r)/2);build(w*2+1,(l+r)/2+1,r);
	tre[w].lc=tre[w*2].lc;tre[w].rc=tre[w*2+1].rc;tre[w].summ=tre[w*2].summ+tre[w*2+1].summ;
	if(tre[w*2].rc==tre[w*2+1].lc)tre[w].summ--;
}
inline void Build(){build(1,1,n);}

void Changee(int w,int l,int r,int s)
{
	if(tre[w].l>r||tre[w].r<l)return;
	if(tre[w].l>=l&&tre[w].r<=r){tre[w].add=s;tre[w].lc=s;tre[w].rc=s;tre[w].summ=1;return;}
	xiachuan(w);
	Changee(w*2,l,r,s);Changee(w*2+1,l,r,s);
	tre[w].lc=tre[w*2].lc;tre[w].rc=tre[w*2+1].rc;tre[w].summ=tre[w*2].summ+tre[w*2+1].summ;
	if(tre[w*2].rc==tre[w*2+1].lc)tre[w].summ--;
}
inline void Change(int l,int r,int s){Changee(1,min(l,r),max(l,r),s);}
inline void change(int x,int y,int s)
{
	int fx=p[x].top,fy=p[y].top;
	while(fx!=fy)
	{
		if(p[fx].dep<p[fy].top)
		{
			swap(x,y);
			swap(fx,fy);
		}
		Change(p[x].pos,p[fx].pos,s);
		x=p[fx].f;fx=p[x].top;
	}
	Change(p[x].pos,p[y].pos,s);
}

int Getcc(int w,int k)
{
	if(tre[w].l==tre[w].r)return tre[w].lc;
	xiachuan(w);
	if(tre[w*2].r>=k&&tre[w*2].l<=k)return Getcc(w*2,k);
	return Getcc(w*2+1,k);
}
inline int Getc(int k){return Getcc(1,k);}
inline int getcc(int w){return Getc(p[w].pos);}

int Getsumm(int w,int l,int r)
{
	if(tre[w].l>r||tre[w].r<l)return 0;
	if(tre[w].l>=l&&tre[w].r<=r)return tre[w].summ;
	xiachuan(w);
	int a=Getsumm(w*2,l,r),b=Getsumm(w*2+1,l,r);
	if(a!=0&&b!=0&&Getc(tre[w*2].r)==Getc(tre[w*2+1].l))return a+b-1;
	return a+b;
}
inline int Getsum(int l,int r){return Getsumm(1,min(l,r),max(l,r));}
inline int getsum(int x,int y)
{
	int summ=0;
	int fx=p[x].top,fy=p[y].top;
	while(fx!=fy)
	{
		if(p[fx].dep<p[fy].top)
		{
			swap(x,y);
			swap(fx,fy);
		}
		summ+=Getsum(p[x].pos,p[fx].pos);
		if(getcc(fx)==getcc(p[fx].f))summ--;
		//cout<<fx<<' '<<p[fx].f<<' '<<getcc(fx)<<' '<<getcc(p[fx].f)<<endl;
		//getcc(fx);
		x=p[fx].f;fx=p[x].top;
	}
	//if(getcc(x)==getcc(y))summ--;
	summ+=Getsum(p[x].pos,p[y].pos);
	return summ;
}

inline void lian(int u,int v)
{
	len++;side[len].v=v;side[len].nex=p[u].head;p[u].head=len;
	len++;side[len].v=u;side[len].nex=p[v].head;p[v].head=len;
}

inline void readd()
{
	len=0;
	int u,v;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>p[i].c;
	for(int i=1;i<n;i++)
	{
		cin>>u>>v;
		lian(u,v);
	}
	p[1].dep=1;
	p[1].f=0;
	p[0].c=-1;
	len=0;
}

void dfs1(int w)
{
	p[w].size=1;p[w].son=-1;
	p[w].top=w;
	
	int v;
	for(int i=p[w].head;i!=0;i=side[i].nex)
	{
		v=side[i].v;
		if(v!=p[w].f)
		{
			p[v].f=w;p[v].dep=p[w].dep+1;
			dfs1(v);
			p[w].size+=p[v].size;
			if(p[w].son==-1||p[v].size>p[p[w].son].size)p[w].son=v;
		}
	}
}

void dfs2(int w)
{
	len++;
	p[w].pos=len;
	c[len]=p[w].c;
	if(p[w].son!=-1)
	{
		p[p[w].son].top=p[w].top;
		dfs2(p[w].son);
	}
	
	int v;
	for(int i=p[w].head;i!=0;i=side[i].nex)
	{
		v=side[i].v;
		if(v!=p[w].f&&v!=p[w].son)
		{
			dfs2(v);
		}
	}
	
}

inline void working()
{
	char f;int x,y,z;
	for(int i=1;i<=m;i++)
	{
		//cout<<i<<','<<endl;
		cin>>f;
		if(f=='C')
		{
			cin>>x>>y>>z;
			change(x,y,z);
		}
		else
		{
			cin>>x>>y;
			///cout<<x<<' '<<y<<' ';
			cout<<getsum(x,y)<<endl;
		}
	}
}

int main()
{
	readd();
	dfs1(1);
	dfs2(1);
	Build();
	//cout<<endl;for(int i=1;i<=n;i++)cout<<i<<' '<<p[i].pos<<endl;
	working();
	return 0;
}

我知道这里写getcc很浪费运行时间，但是反正也不会TLE，码量思考量也小，很适合我这个萌新