【动态开点线段树&树链剖分】【[SDOI2014]旅行】

题目传送门

写篇题解巩固一下动态开点线段树和树链剖分，并附上模板

一、动态开点线段树

在某些题目中我们不需要把线段树的所有节点都建立出来，而是当用到某个节点时才建立该节点，从而节省空间。

用到动态开点线段树的题，一般有几个特点：

1. 用普通线段树在时间上可以通过此题，但是空间上会爆

2. 通过分析题目，能够确保，线段树不可能建满，即树的大小与询问有关。例如本题，最初只有n个点，若对每种宗教建一颗大小为n的线段树，那么最初结点总数最多为nlogn，加上后面的单点修改，总结点数最多为（q+n）log n，这是完全开的下的。

几个注意事项：

1. 每次单点插入最多增加logn个点，每次区间修改最多会增加2logn的点，可以用来估算线段树开的结构体大小
2. 动态开点线段树最好不在结构体中记录区间的左右端点，原因很简单，之所以动态开点就是为了省空间，若再记录不必要的区间端点，就有些浪费了。

二、树剖

没啥好说的，就是两遍dfs，考点都在维护链的数据结构上，熟悉模板即可。

三、对于本题

发现很难用一颗线段树同时维护每个宗教的信息，但发现，每个宗教之间的信息互不影响，于是对每个宗教分别建一颗动态开点线段树即可。

Code

#include<bits/stdc++.h>
using namespace std;

inline int read()
{
	register int x=0,w=1;
	register char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') {w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*w;
}
const int N=1e5+100;
int n,q,rt[N];
int w[N],c[N],top[N],dfn[N],id[N],siz[N],hs[N],d[N],fa[N],tot;
struct node{
	int ls,rs,sum,maxn;
}t[N*40];
vector<int>v[N];
void dfs1(int x)
{
	siz[x]=1;
	for(int i=0;i<v[x].size();++i)
	{
		int y=v[x][i];
		if(y==fa[x]) continue;
		fa[y]=x;
		d[y]=d[x]+1;
		dfs1(y);
		siz[x]+=siz[y];
		if(siz[y]>siz[hs[x]]) hs[x]=y;
	}
}
void dfs2(int x)
{
	dfn[x]=++tot;
	id[tot]=x;
	if(hs[x]){
		top[hs[x]]=top[x];
		dfs2(hs[x]);
	}
	for(int i=0;i<v[x].size();++i)
	{
		int y=v[x][i];
		if(dfn[y]) continue;
		top[y]=y;
		dfs2(y);
	}
}
void pushup(int x)
{
	t[x].maxn=max(t[t[x].ls].maxn,t[t[x].rs].maxn);
	t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum;
}
void change(int x,int pos,int val,int l,int r)
{
	if(l==r){
		t[x].sum=t[x].maxn=t[x].sum+val;
		return;
	}
	int mid=l+r>>1;
	if(pos<=mid){
		if(!t[x].ls) t[x].ls=++tot;
		change(t[x].ls,pos,val,l,mid);
	}
	else{
		if(!t[x].rs) t[x].rs=++tot;
		change(t[x].rs,pos,val,mid+1,r);
	}
	pushup(x);
}
void dfs(int x)
{
	change(rt[c[x]],dfn[x],w[x],1,n);
	for(int i=0;i<v[x].size();++i)
	{
		int y=v[x][i];
		if(y==fa[x]) continue;
		dfs(y);
	}
}
char op[3];
int querysum(int x,int l,int r,int L,int R)
{
	if(L>=l&&R<=r){
		return t[x].sum;
	}
	int mid=L+R>>1;
	int res=0;
	if(l<=mid&&t[x].ls) {
		res+=querysum(t[x].ls,l,r,L,mid);
	}
	if(r>mid&&t[x].rs){
		res+=querysum(t[x].rs,l,r,mid+1,R);
	}
	return res;
}
int asksum(int x,int y)
{
	int root=rt[c[x]];
	int res=0;
	while(top[x]!=top[y])
	{
		if(d[top[x]]<d[top[y]]) swap(x,y);
		res+=querysum(root,dfn[top[x]],dfn[x],1,n);
		x=fa[top[x]];
	}
	if(d[x]>d[y]) swap(x,y);
	return res+querysum(root,dfn[x],dfn[y],1,n);
}
int querymax(int x,int l,int r,int L,int R)
{
	if(L>=l&&R<=r){
		return t[x].maxn;
	}
	int mid=L+R>>1;
	int res=0;
	if(l<=mid&&t[x].ls) {
		res=max(res,querymax(t[x].ls,l,r,L,mid));
	}
	if(r>mid&&t[x].rs){
		res=max(res,querymax(t[x].rs,l,r,mid+1,R));
	}
	return res;
}
int askmax(int x,int y)
{
	int root=rt[c[x]];
	int res=0;
	while(top[x]!=top[y])
	{
		if(d[top[x]]<d[top[y]]) swap(x,y);
		res=max(res,querymax(root,dfn[top[x]],dfn[x],1,n));
		x=fa[top[x]];
	}
	if(d[x]>d[y]) swap(x,y);
	return max(res,querymax(root,dfn[x],dfn[y],1,n));
}
int main()
{
    n=read();q=read();
    for(int i=1;i<=n;++i)
    {
    	w[i]=read();
    	c[i]=read();
	}
	for(int i=1;i<n;++i)
	{
		int x=read(),y=read();
		v[x].push_back(y);
		v[y].push_back(x);
	}
	d[1]=1;
	dfs1(1);
	top[1]=1;
	dfs2(1);
	tot=0;
	for(int i=1;i<=n;++i) rt[c[i]]=++tot;
	dfs(1);
	for(int i=1;i<=q;++i)
	{
		scanf("%s",op);
		int x=read(),y=read();
		if(!strcmp(op,"CC")){
			change(rt[c[x]],dfn[x],-w[x],1,n);
			c[x]=y;
			if(rt[y]==0) rt[y]=++tot;
			change(rt[c[x]],dfn[x],w[x],1,n);
		}
		else if(!strcmp(op,"CW"))
		{
			change(rt[c[x]],dfn[x],y-w[x],1,n);
			w[x]=y;
		}
		else if(!strcmp(op,"QS"))
		{
			printf("%d\n",asksum(x,y));
		}
		else 
		{
			printf("%d\n",askmax(x,y));
		}
	}
	return 0;
}