【刷题】BZOJ 3531 [Sdoi2014]旅行

Description

S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足

从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。

在S国的历史上常会发生以下几种事件：

”CC x c”：城市x的居民全体改信了c教；

”CW x w”：城市x的评级调整为w;

”QS x y”：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级总和；

”QM x y”：一位旅行者从城市x出发，到城市y，并记下了途中留宿过

的城市的评级最大值。

由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。

Input

输入的第一行包含整数N，Q依次表示城市数和事件数。

接下来N行，第i+l行两个整数Wi，Ci依次表示记录开始之前，城市i的

评级和信仰。

接下来N-1行每行两个整数x，y表示一条双向道路。

接下来Q行，每行一个操作，格式如上所述。

Output

对每个QS和QM事件，输出一行，表示旅行者记下的数字。

Sample Input

5 6

3 1

2 3

1 2

3 3

5 1

1 2

1 3

3 4

3 5

QS 1 5

CC 3 1

QS 1 5

CW 3 3

QS 1 5

QM 2 4

Sample Output

8

9

11

3

HINT

N，Q < =10^5 ， C < =10^5

数据保证对所有QS和QM事件，起点和终点城市的信仰相同；在任意时

刻，城市的评级总是不大于10^4的正整数，且宗教值不大于C。

Solution

树剖后开 \(C\) 棵线段树，维护每一种宗教的信息

\(C\) 太大，用动态开点

#include<bits/stdc++.h>

#define ui unsigned int

#define ll long long

#define db double

#define ld long double

#define ull unsigned long long

const int MAXN=100000+10;

int n,q,val[MAXN],peo[MAXN],e,beg[MAXN],nex[MAXN<<1],to[MAXN<<1],top[MAXN],size[MAXN],hson[MAXN],dep[MAXN],fa[MAXN],st[MAXN],anssum,ansmax,cnt;

template<typename T> inline void read(T &x)

{

	T data=0,w=1;

	char ch=0;

	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();

	if(ch=='-')w=-1,ch=getchar();

	while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();

	x=data*w;

}

template<typename T> inline void write(T x,char ch='\0')

{

	if(x<0)putchar('-'),x=-x;

	if(x>9)write(x/10);

	putchar(x%10+'0');

	if(ch!='\0')putchar(ch);

}

template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}

template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}

template<typename T> inline T min(T x,T y){return x<y?x:y;}

template<typename T> inline T max(T x,T y){return x>y?x:y;}

#define Mid ((l+r)>>1)

#define lson l,Mid

#define rson Mid+1,r

struct Segment_Tree{

	int lc[MAXN<<5],rc[MAXN<<5],Mx[MAXN<<5],root[MAXN],cnt,sum[MAXN<<5];

	inline void PushUp(int rt)

	{

		Mx[rt]=max(Mx[lc[rt]],Mx[rc[rt]]);

		sum[rt]=sum[lc[rt]]+sum[rc[rt]];

	}

	inline void Update(int &rt,int l,int r,int ps,int k)

	{

		if(!rt)rt=++cnt;

		if(l==r)Mx[rt]=sum[rt]=k;

		else

		{

			if(ps<=Mid)Update(lc[rt],lson,ps,k);

			else Update(rc[rt],rson,ps,k);

			PushUp(rt);

		}

	}

	inline void Query(int rt,int l,int r,int L,int R)

	{

		if(!rt)return ;

		if(L<=l&&r<=R)anssum+=sum[rt],chkmax(ansmax,Mx[rt]);

		else

		{

			if(L<=Mid)Query(lc[rt],lson,L,R);

			if(R>Mid)Query(rc[rt],rson,L,R);

		}

	}

};

Segment_Tree T;

#undef Mid

#undef lson

#undef rson

inline void insert(int x,int y)

{

	to[++e]=y;

	nex[e]=beg[x];

	beg[x]=e;

}

inline void dfs1(int x,int f)

{

	int res=0;

	fa[x]=f;size[x]=1;dep[x]=dep[f]+1;

	for(register int i=beg[x];i;i=nex[i])

		if(to[i]==f)continue;

		else

		{

			dfs1(to[i],x);

			size[x]+=size[to[i]];

			if(size[to[i]]>res)res=size[to[i]],hson[x]=to[i];

		}

}

inline void dfs2(int x,int tp)

{

	top[x]=tp;st[x]=++cnt;

	T.Update(T.root[peo[x]],1,n,st[x],val[x]);

	if(hson[x])dfs2(hson[x],tp);

	for(register int i=beg[x];i;i=nex[i])

		if(to[i]==fa[x]||to[i]==hson[x])continue;

		else dfs2(to[i],to[i]);

}

inline void Getans(int u,int v)

{

	int people=peo[u];

	anssum=0;ansmax=0;

	while(top[u]!=top[v])

	{

		if(dep[top[u]]<dep[top[v]])std::swap(u,v);

		T.Query(T.root[people],1,n,st[top[u]],st[u]);

		u=fa[top[u]];

	}

	if(dep[u]<dep[v])std::swap(u,v);

	T.Query(T.root[people],1,n,st[v],st[u]);

}

int main()

{

	read(n);read(q);

	for(register int i=1;i<=n;++i)read(val[i]),read(peo[i]);

	for(register int i=1;i<n;++i)

	{

		int u,v;read(u);read(v);

		insert(u,v);insert(v,u);

	}

	dfs1(1,0);

	dfs2(1,1);

	while(q--)

	{

		char opt[3];scanf("%s",opt);

		if(!strcmp(opt,"CC"))

		{

			int x,c;read(x);read(c);

			T.Update(T.root[peo[x]],1,n,st[x],0);

			T.Update(T.root[peo[x]=c],1,n,st[x],val[x]);

		}

		if(!strcmp(opt,"CW"))

		{

			int x,w;read(x);read(w);

			T.Update(T.root[peo[x]],1,n,st[x],val[x]=w);

		}

		if(!strcmp(opt,"QS"))

		{

			int x,y;read(x);read(y);

			Getans(x,y);write(anssum,'\n');

		}

		if(!strcmp(opt,"QM"))

		{

			int x,y;read(x);read(y);

			Getans(x,y);write(ansmax,'\n');

		}

	}

	return 0;

}

巴特西