链接：传送门
-
3531: [Sdoi2014]旅行
Time Limit: 40 Sec Memory Limit: 512 MB Submit: 3406 Solved: 1528 [Submit][Status][Discuss]
Description
S S S国有 N N N个城市，编号从 1 1 1到 N N N。城市间用 N − 1 N-1 N−1条双向道路连接，满足
从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便，我们用不同的正整数代表各种宗教， S S S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。 S S S国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。
在S国的历史上常会发生以下几种事件：
” C C x c CC\ x\ c CC x c”：城市x的居民全体改信了 c c c教；
” C W x w CW\ x\ w CW x w”：城市x的评级调整为 w w w;
” Q S x y QS\ x\ y QS x y”：一位旅行者从城市 x x x出发，到城市 y y y，并记下了途中留宿过的城市的评级总和；
” Q M x y QM\ x\ y QM x y”：一位旅行者从城市 x x x出发，到城市 y y y，并记下了途中留宿过
的城市的评级最大值。
由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。 为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。
Input
输入的第一行包含整数 N ， Q N，Q N，Q依次表示城市数和事件数。
接下来N行，第i+l行两个整数 W i ， C i W_i，C_i Wi，Ci依次表示记录开始之前，城市i的
评级和信仰。
接下来 N − 1 N-1 N−1行每行两个整数 x ， y x，y x，y表示一条双向道路。
接下来 Q Q Q行，每行一个操作，格式如上所述。
Output
对每个 Q S QS QS和 Q M QM 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 < = 1 0 5 ， C < = 1 0 5 N，Q < =10^5 ， C < =10^5 N，Q<=105，C<=105
数据保证对所有 Q S QS QS和 Q M QM QM事件，起点和终点城市的信仰相同；在任意时
刻，城市的评级总是不大于 1 0 4 10^4 104的正整数，且宗教值不大于 C C C。
Source
R o u n d 1 D a y 1 Round\ 1\ Day\ 1 Round 1 Day 1
题意：
给你一颗无根树，每个节点代表一座城市，每座城市信仰的宗教 为 C i C_i Ci，城市评级 W i W_i Wi ,实现如下操作：
- 修改城市 x x x的评级
- 修改城市 x x x的信仰
- 查询从城市 x x x到城市 y y y的最短路径上的所有信仰宗教 C y C_y Cy的城市的评级最大值
- 查询从城市 x x x到城市 y y y的最短路径上的所有信仰宗教 C y C_y Cy的城市的评级之和
题解
- 1A还是很舒服的233
- 因为最多1e5种宗教，可以考虑先树剖出每个节点编号，然后对于每个宗教，用一颗线段树（动态开点）维护这个宗教所在的所有城市对应的树剖出来的下标，这样就可以完成对于亮点之间特定的宗教对应的最大值以及和，复杂度 n log n n\log n nlogn（但是如果是要求两点间所有节点评级和呢？暂时只知道 n 2 n^2 n2 log n \log n logn的做法，即枚举一下所有两点之间的城市信仰，然后对每一个信仰再去更新）
附代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int L=1;
const int R=1e5+5;
vector<int> vec[maxn];
int n,m,u,v,c[maxn],w[maxn];
char opt[20];
// 树剖用
struct dynamic_segment_tree{
int roo[maxn],tot; // 为每一个宗教维护一颗动态开点线段树，每个宗教在线段树中的位置为其在树剖时的编号
struct node{
int ls,rs,sum,maxx;
}tree[maxn*20];
dynamic_segment_tree(){
tot=0;
memset(roo,0,sizeof(roo));
memset(tree,0,sizeof(tree));
}
void pushup(int id){
tree[id].sum=tree[tree[id].ls].sum+tree[tree[id].rs].sum;
tree[id].maxx=max(tree[tree[id].ls].maxx,tree[tree[id].rs].maxx);
}
void update(int l,int r,int k,int val,int id){ //l,r为总区间,k为需要插入的位置，id为当前节点编号
if(l==r){ //插点操作
tree[id].sum=tree[id].maxx=val;
return;
}
int mid=(l+r)>>1;
if(k<=mid){
if(!tree[id].ls) tree[id].ls=++tot;
update(l,mid,k,val,tree[id].ls);
}else{
if(!tree[id].rs) tree[id].rs=++tot;
update(mid+1,r,k,val,tree[id].rs);
}
pushup(id);
}
int query_sum(int l,int r,int le,int ri,int id){ //l,r总区间，le,ri待查询区间，id当前节点编号
int ans=0;
if(le<=l&&ri>=r) return tree[id].sum;
int mid=(l+r)>>1;
if(le<=mid&&tree[id].ls) ans+=query_sum(l,mid,le,ri,tree[id].ls);
if(ri>mid&&tree[id].rs) ans+=query_sum(mid+1,r,le,ri,tree[id].rs);
return ans;
}
int query_max(int l,int r,int le,int ri,int id){
int ans=0;
if(le<=l&&ri>=r) return tree[id].maxx;
int mid=(l+r)>>1;
if(le<=mid&&tree[id].ls) ans=max(ans,query_max(l,mid,le,ri,tree[id].ls));
if(ri>mid&&tree[id].rs) ans=max(ans,query_max(mid+1,r,le,ri,tree[id].rs));
return ans;
}
void point_delete(int l,int r,int k,int id){
if(l==r){
tree[id].maxx=tree[id].sum=0;
return;
}
int mid=(l+r)>>1;
if(k<=mid) point_delete(l,mid,k,tree[id].ls);
else point_delete(mid+1,r,k,tree[id].rs);
pushup(id);
}
}data;
struct tree{
int h[maxn],fa[maxn],top[maxn],id[maxn],son[maxn],siz[maxn],rk[maxn],tot;
tree(){
tot=0;
memset(son,0,sizeof(son));
memset(h,0,sizeof(h));
}
void build(){
dfs1(1,0,1);dfs2(1,1);
for(int i=1;i<=n;i++){
if(!data.roo[c[i]]) data.roo[c[i]]=++data.tot;
data.update(L,R,id[i],w[i],data.roo[c[i]]);
}
}
void dfs1(int cur,int fath,int he){ //dfs(root,0,1)
h[cur]=he;fa[cur]=fath;siz[cur]=1;
for(int i=0;i<vec[cur].size();i++){
if(vec[cur][i]!=fath){
dfs1(vec[cur][i],cur,he+1);
siz[cur]+=siz[vec[cur][i]];
if(siz[vec[cur][i]]>siz[son[cur]]) son[cur]=vec[cur][i];
}
}
}
void dfs2(int cur,int topp){ //dfs2(root,root)
id[cur]=++tot;rk[tot]=cur;top[cur]=topp;
if(son[cur]) dfs2(son[cur],topp);
for(int i=0;i<vec[cur].size();i++){
if(vec[cur][i]!=fa[cur]&&vec[cur][i]!=son[cur]){
dfs2(vec[cur][i],vec[cur][i]);
}
}
}
//区间和
int query_sum(int x,int y){
int goal=c[y];
int topx=top[x],topy=top[y];int ans=0;
while(topx!=topy){
if(h[topx]>=h[topy]){
ans=(ans+data.query_sum(L,R,id[topx],id[x],data.roo[goal]));
x=fa[topx],topx=top[x];
}else{
ans=(ans+data.query_sum(L,R,id[topy],id[y],data.roo[goal]));
y=fa[topy],topy=top[y];
}
}
ans=(ans+data.query_sum(L,R,min(id[x],id[y]),max(id[x],id[y]),data.roo[goal]));
return ans;
}
//区间最大值
int query_max(int x,int y){
int goal=c[y];
int topx=top[x],topy=top[y];int ans=-1e9;
while(topx!=topy){
if(h[topx]>=h[topy]){
ans=max(ans,data.query_max(L,R,id[topx],id[x],data.roo[goal]));
x=fa[topx],topx=top[x];
}else{
ans=max(ans,data.query_max(L,R,id[topy],id[y],data.roo[goal]));
y=fa[topy],topy=top[y];
}
}
ans=max(ans,data.query_max(L,R,min(id[x],id[y]),max(id[x],id[y]),data.roo[goal]));
return ans;
}
//单点修改
void update_c(int x,int val){
data.point_delete(L,R,id[x],data.roo[c[x]]);
if(!data.roo[val]) data.roo[val]=++data.tot;
data.update(L,R,id[x],w[x],data.roo[val]);
c[x]=val;
}
void update_w(int x,int val){
w[x]=val;
data.update(L,R,id[x],val,data.roo[c[x]]);
}
void debug(){
printf("son[]: "); for(int i=1;i<=n;i++) printf("%d%c",son[i],i==n?'\n':' ');
printf("id[]: ");for(int i=1;i<=n;i++) printf("%d%c",id[i],i==n?'\n':' ');
}
}chain;
int main()
{
scanf("%d %d",&n,&m);
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);
vec[u].push_back(v);
vec[v].push_back(u);
}
chain.build();
for(int i=1;i<=m;i++){
scanf("%s %d %d",opt+1,&u,&v);
if(opt[1]=='C'&&opt[2]=='C') chain.update_c(u,v);
else if(opt[1]=='C'&&opt[2]=='W') chain.update_w(u,v);
else if(opt[1]=='Q'&&opt[2]=='S') printf("%d\n",chain.query_sum(u,v));
else printf("%d\n",chain.query_max(u,v));
}
}
![codeforces E. Tourists （树链剖分+tarjan）[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)