連結：傳送門
-
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=)