3531: [Sdoi2014]旅行
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 837 Solved: 426
[Submit][Status][Discuss]
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。
Source
在普通的树链剖分基础上加了一个宗教的限制，但我们发现宗教个数在105范围内，我们可以对每个宗教开一个线段树，然后只要访问到的点开点就可以了，这样就不会超内存了。挺水的
代码：
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{int l,r,sum,max;}tr[10000010];
int n,q,edgenum,u,v,tot,cnt,x,y,z,ans;
int f[200010],d[200010],num[200010],son[200010],top[200010],tid[200010],pre[200010],root[200010];
int vet[200010],next[200010],head[200010],w[200010],c[200010];
char opt[20];
void add(int u,int v)
{
vet[++edgenum]=v;
next[edgenum]=head[u];
head[u]=edgenum;
}
void dfs(int u,int fa,int dep)
{
f[u]=fa;
d[u]=dep;
num[u]=1;
int maxnum=0;
for (int e=head[u];e;e=next[e])
{
int v=vet[e];
if (v!=fa)
{
dfs(v,u,dep+1);
num[u]+=num[v];
if (num[v]>maxnum){maxnum=num[v];son[u]=v;}
}
}
}
void dfs(int u,int number)
{
top[u]=number;
tid[u]=++tot;
pre[tot]=u;
if (!son[u]) return;
dfs(son[u],number);
for (int e=head[u];e;e=next[e])
{
int v=vet[e];
if (v!=f[u]&&v!=son[u]) dfs(v,v);
}
}
int lca(int u,int v)
{
for (;top[u]!=top[v];u=f[top[u]])if (d[top[u]]<d[top[v]]) swap(u,v);
if (d[u]<d[v]) return u;return v;
}
void change(int l,int r,int &p,int x,int val)
{
if (!p) p=++cnt;
if (l==r){tr[p].max=tr[p].sum=val;return;}
int mid=(l+r)>>1;
if (x<=mid) change(l,mid,tr[p].l,x,val);else change(mid+1,r,tr[p].r,x,val);
tr[p].max=max(tr[tr[p].l].max,tr[tr[p].r].max);
tr[p].sum=tr[tr[p].l].sum+tr[tr[p].r].sum;
}
int askmax(int l,int r,int p,int x,int y)
{
if (!p) return 0;
if (l==x&&y==r) return tr[p].max;
int mid=(l+r)>>1;
if (y<=mid) return askmax(l,mid,tr[p].l,x,y);else
if (x>mid) return askmax(mid+1,r,tr[p].r,x,y);else
return max(askmax(l,mid,tr[p].l,x,mid),askmax(mid+1,r,tr[p].r,mid+1,y));
}
int asksum(int l,int r,int p,int x,int y)
{
if (!p) return 0;
if (l==x&&y==r) return tr[p].sum;
int mid=(l+r)>>1;
if (y<=mid) return asksum(l,mid,tr[p].l,x,y);else
if (x>mid) return asksum(mid+1,r,tr[p].r,x,y);else
return asksum(l,mid,tr[p].l,x,mid)+asksum(mid+1,r,tr[p].r,mid+1,y);
}
int getsum(int u,int v,int c)
{
int ans=0;
while (top[u]!=top[v])
{
ans+=asksum(1,n,root[c],tid[top[u]],tid[u]);
u=f[top[u]];
}
ans+=asksum(1,n,root[c],tid[v],tid[u]);
return ans;
}
int getmax(int u,int v,int c)
{
int ans=0;
while (top[u]!=top[v])
{
ans=max(ans,askmax(1,n,root[c],tid[top[u]],tid[u]));
u=f[top[u]];
}
ans=max(ans,askmax(1,n,root[c],tid[v],tid[u]));
return ans;
}
int main()
{
scanf("%d%d",&n,&q);
for (int i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]);
for (int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs(1,0,1);
dfs(1,1);
for (int i=1;i<=n;i++) change(1,n,root[c[i]],tid[i],w[i]);
while (q--)
{
scanf("%s",opt);
scanf("%d%d",&x,&y);
if (opt[0]=='C')
{
if (opt[1]=='C')
{
change(1,n,root[c[x]],tid[x],0);
c[x]=y;
change(1,n,root[c[x]],tid[x],w[x]);
}else {change(1,n,root[c[x]],tid[x],y);w[x]=y;}
}else
{
z=lca(x,y);
if (opt[1]=='S')
{
ans=getsum(x,z,c[x])+getsum(y,z,c[x]);
if (c[x]==c[z]) ans-=w[z];
printf("%d\n",ans);
}else printf("%d\n",max(getmax(x,z,c[x]),getmax(y,z,c[x])));
}
}
}
.gif)
.gif)
.gif)
.gif)
