B20J_3231_[SDOI2014]旅行_树链剖分+线段树
题意：
S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，城市信仰不同的宗教，为了方便，我们用不同的正整数代表各种宗教。
S国的居民常常旅行，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国*为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。
以下几种操作：
• "CC x c"：城市x的居民全体改信了c教；
• "CW x w"：城市x的评级调整为w；
• "QS x y"：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级总和；
• "QM x y"：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级最大值。
分析：对每个宗教开一个线段树（动态开点）。CC操作时删除原来宗教所在线段树上该点的值，在新的宗教所在线段树中加入该点的值。
注意：
1.在查询时遇到一个空点要return。
2.修改时线段树上的值和本身的值都要修改
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N=100001;
int head[N],to[N<<1],nxt[N<<1],val[N],b[N],cnt;
int son[N],top[N],dep[N],fa[N],siz[N],idx[N],tot,cet;
int tree[N],lson[N*20],rson[N*20],d[N*20],m[N*20];
void add(int u,int v)
{
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
int n,q;
char s[10];
void dfs1(int x,int y)
{
fa[x]=y;
siz[x]=1;
dep[x]=dep[y]+1;
for(int i=head[x];i;i=nxt[i])
{
if(to[i]!=y)
{
dfs1(to[i],x);
siz[x]+=siz[to[i]];
if(siz[to[i]]>siz[son[x]])
{
son[x]=to[i];
}
}
}
}
void dfs2(int x,int t)
{
top[x]=t;
idx[x]=++tot;
if(son[x])dfs2(son[x],t);
for(int i=head[x];i;i=nxt[i])
{
if(to[i]!=fa[x]&&to[i]!=son[x])
{
dfs2(to[i],to[i]);
}
}
}
void up(int l,int r,int x,int y,int &p)
{
if(!p)p=++cet;
if(l==r)
{
d[p]=m[p]=y;
return ;
}
int mid=l+r>>1;
if(x<=mid)up(l,mid,x,y,lson[p]);
else up(mid+1,r,x,y,rson[p]);
d[p]=d[lson[p]]+d[rson[p]];
m[p]=max(m[lson[p]],m[rson[p]]);
}
int qsum(int l,int r,int x,int y,int &p)
{
if(p==0)return 0;
if(x<=l&&r<=y)
{
return d[p];
}
int mid=l+r>>1;
int re=0;
if(x<=mid)
{
re+=qsum(l,mid,x,y,lson[p]);
}
if(y>mid)
{
re+=qsum(mid+1,r,x,y,rson[p]);
}
return re;
}
int qmax(int l,int r,int x,int y,int &p)
{
if(p==0)return 0;
if(x<=l&&r<=y)
{
return m[p];
}
int re=0;
int mid=l+r>>1;
if(x<=mid)
{
re=max(re,qmax(l,mid,x,y,lson[p]));
}
if(y>mid)
{
re=max(re,qmax(mid+1,r,x,y,rson[p]));
}
return re;
}
int main()
{
scanf("%d%d",&n,&q);
int x,y;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&val[i],&b[i]);
}
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=n;i++)
{
up(1,n,idx[i],val[i],tree[b[i]]);
}
for(int i=1;i<=q;i++)
{
scanf("%s%d%d",s,&x,&y);
if(s[1]=='C')
{
up(1,n,idx[x],0,tree[b[x]]);
b[x]=y;
up(1,n,idx[x],val[x],tree[b[x]]);
}
else if(s[1]=='S')
{
int re=0,rt=b[x];
while(top[x]!=top[y])
{
if(dep[top[x]]>dep[top[y]])
swap(x,y);
re+=qsum(1,n,idx[top[y]],idx[y],tree[rt]);
y=fa[top[y]];
}
if(dep[x]<dep[y])swap(x,y);
re+=qsum(1,n,idx[y],idx[x],tree[rt]);
printf("%d\n",re);
}
else if(s[1]=='W')
{
up(1,n,idx[x],y,tree[b[x]]);
val[x]=y;
}
else
{
int re=0,rt=b[x];
while(top[x]!=top[y])
{
if(dep[top[x]]>dep[top[y]])
swap(x,y);
re=max(re,qmax(1,n,idx[top[y]],idx[y],tree[rt]));
y=fa[top[y]];
}
if(dep[x]<dep[y])swap(x,y);
re=max(re,qmax(1,n,idx[y],idx[x],tree[rt]));
printf("%d\n",re);
}
}
}
/***************************************************************
Problem: 2456
User: 20170105
Language: C++
Result: Accepted
Time:524 ms
Memory:42248 kb
****************************************************************/