BZOJ 3531 旅行

Link

Solution

Code

//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=1e5+10,NLOGN=MAXN*30,INF=0x1f1f1f1f;
using std::max;
using std::min;
using std::swap;

struct Edge{int to,pre;}e[MAXN<<1];int id[MAXN],ec;
void Adde(int f,int t)
{
	e[++ec].to=t;e[ec].pre=id[f];id[f]=ec;
	e[++ec].to=f;e[ec].pre=id[t];id[t]=ec;
}
struct Data
{
	int maxv,sumv;
	Data(){maxv=-INF,sumv=0;}
	Data(int _maxv,int _sumv):maxv(_maxv),sumv(_sumv){}
};
Data Merge(Data a,Data b){return Data(max(a.maxv,b.maxv),a.sumv+b.sumv);}
struct SegNode
{
	SegNode *son[2];
	Data v;int cnt;
	void up()
	{
		v=Merge(son[0]?son[0]->v:Data(),son[1]?son[1]->v:Data());
		cnt=(son[0]?son[0]->cnt:0)+(son[1]?son[1]->cnt:0);
	}
};
namespace SegOpt
{
	SegNode *ME=new SegNode[NLOGN];
	//有了这一句就高亮不了了。。。
    //SegNode *newNode(Data v=Data())
	{
		static SegNode* cur;
		cur=ME++;cur->v=v;cur->son[0]=cur->son[1]=0;cur->cnt=1;
		return cur;
	}
	void Edit(SegNode *&pos,int L,int R,int goal,Data dv,int dc)
	{
		if(!pos) pos=newNode();
		if(L==R)
		{
			pos->v=dv;
			pos->cnt=dc;
		}
		else
		{
			int MID=(L+R)>>1;
			if(goal<=MID) Edit(pos->son[0],L,MID,goal,dv,dc);
			else Edit(pos->son[1],MID+1,R,goal,dv,dc);
			pos->up();
		}
	}
	Data Access(SegNode *&pos,int L,int R,int l,int r)
	{
		if(!pos || pos->cnt==0) return Data();
		if(L==l && R==r) return pos->v;
		else
		{
			int MID=(L+R)>>1;
			if(r<=MID) return Access(pos->son[0],L,MID,l,r);
			else if(MID+1<=l) return Access(pos->son[1],MID+1,R,l,r);
			else return Merge(Access(pos->son[0],L,MID,l,MID),Access(pos->son[1],MID+1,R,MID+1,r));
		}
	}
}
using namespace SegOpt;
struct TreapNode
{
	TreapNode *son[2];
	SegNode *root;int v,py;
};
namespace TreapOpt
{
	const int P=1e5+7;
	TreapNode *ME=new TreapNode[NLOGN];
	TreapNode *newNode(int v)
	{
		static TreapNode *cur;
		cur=ME++;cur->v=v;cur->root=0;cur->py=rand()%P;
		cur->son[0]=cur->son[1]=0;
		return cur;
	}
	void trans(TreapNode *&pos,int d)
	{
		TreapNode *s=pos->son[d];
		pos->son[d]=s->son[!d];
		s->son[!d]=pos;
		pos=s;
	}
	int adjust(TreapNode *&pos)
	{
		int d=(pos->son[0]?pos->son[0]->py:P)>(pos->son[1]?pos->son[1]->py:P);
		if(pos->son[d] && pos->son[d]->py<pos->py) trans(pos,d),d^=1;
		else d=-1;
		return d;
	}
	TreapNode *Insert(TreapNode *&pos,int v)
	{
		if(!pos)
			return pos=newNode(v);
		else
		{
			int jud=pos->v<v;
			TreapNode *p=Insert(pos->son[jud],v);
			adjust(pos);
			return p;
		}
	}
	TreapNode *Find(TreapNode *pos,int v)
	{
		while(pos)
		{
			if(pos->v==v)
				return pos;
			else pos=pos->son[pos->v<v];
		}
		return 0;
	}
	void out(TreapNode *pos)
	{
		if(!pos) return;
		out(pos->son[0]);
		printf("%d ",pos->v);
		out(pos->son[1]);
	}
	void print(TreapNode *pos)
	{
		puts("BEGIN");
		out(pos);
		puts("\nEND");
	}
}
using namespace TreapOpt;
struct Part
{
	TreapNode *root;
	int sz,top;
}part[MAXN],*cn[MAXN];
int rc,dep[MAXN],sz[MAXN],rnk[MAXN],fa[MAXN];
void DFS(int pos)
{
	int mx=-1;sz[pos]=1;
	for(int i=id[pos];i;i=e[i].pre)
	{
		int u=e[i].to;
		if(fa[pos]==u) continue;
		fa[u]=pos;dep[u]=dep[pos]+1;
		DFS(u);
		sz[pos]+=sz[u];
		if(mx==-1 || sz[u]>sz[mx]) mx=u;
	}
	if(!pos) mx=-1;
	for(int i=id[pos];i;i=e[i].pre)
	{
		int u=e[i].to;
		if(fa[pos]==u) continue;
		if(u==mx)
		{
			cn[pos]=cn[u];
			rnk[pos]=rnk[u]+1;
		}
		else
		{
			cn[u]->top=u;
			cn[u]->sz=rnk[u];
		}
	}
	if(pos && !cn[pos])
	{
		cn[pos]=part+ ++rc;
		rnk[pos]=1;
	}
}
int val[MAXN],color[MAXN];
void Change(int pos,int w,int c)
{
	TreapNode *po=Find(cn[pos]->root,color[pos]),
			  *pn=Find(cn[pos]->root,c);
	if(po) Edit(po->root,1,cn[pos]->sz,rnk[pos],Data(),0);
	if(!pn) pn=Insert(cn[pos]->root,c);
	Edit(pn->root,1,cn[pos]->sz,rnk[pos],Data(w,w),1);
	val[pos]=w,color[pos]=c;
}
Data Query(int p1,int p2)
{
	Data res=Data();int c=color[p1];//val..
	while(cn[p1]!=cn[p2])
	{
		if(dep[cn[p1]->top]<dep[cn[p2]->top]) swap(p1,p2);
		TreapNode *p=Find(cn[p1]->root,c);
		if(p)
			res=Merge(res,Access(p->root,1,cn[p1]->sz,rnk[p1],cn[p1]->sz));
		p1=fa[cn[p1]->top];//if(!p1) p1=1;
	}
	if(rnk[p1]>rnk[p2]) swap(p1,p2);
	TreapNode *p=Find(cn[p1]->root,c);
	if(p)
		res=Merge(res,Access(p->root,1,cn[p1]->sz,rnk[p1],rnk[p2]));//cn[p1]->sz
	if(res.maxv==-INF) res=Data(val[p1],val[p1]);
	return res;
}
int main()
{
	//freopen("input","r",stdin);
	static int w[MAXN],c[MAXN];
	int n,m;get(n),get(m);
	for(int i=1;i<=n;i++) get(w[i]),get(c[i]);
	for(int i=1;i<=n-1;i++)
	{
		int x,y;get(x),get(y);
		Adde(x,y);
	}
	Adde(0,1);
	DFS(0);
	for(int i=1;i<=n;i++) Change(i,w[i],c[i]);
	for(int i=1;i<=m;i++)
	{
		char opt[5];int x,y,w,c;
		scanf("%s",opt);
		switch(opt[1])
		{
			case 'C':
				get(x),get(c);
				Change(x,val[x],c);//val[i]
				break;
			case 'W':
				get(x),get(w);
				Change(x,w,color[x]);
				break;
			case 'S':
				get(x),get(y);
				printf("%d\n",Query(x,y).sumv);
				break;
			case 'M':
				get(x),get(y);
				printf("%d\n",Query(x,y).maxv);
				break;
		}
	}
	return 0;
}
/* AC Record(Bugs) *
 * WA  psz
 * WA  1
 * WA p1==p2
 *
 * * * * * * * * * */