「BZOJ3531」[Sdoi2014]旅行--树剖好题

链接：传送门

• 3531: [Sdoi2014]旅行

Description

$S$国有$N$个城市，编号从$1$到$N$。城市间用$N-1$条双向道路连接，满足
从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便，我们用不同的正整数代表各种宗教， $S$国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。$S$国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。
在S国的历史上常会发生以下几种事件：
”$CCxc$”：城市x的居民全体改信了$c$教；
”$CWxw$”：城市x的评级调整为$w$;
”$QSxy$”：一位旅行者从城市$x$出发，到城市$y$，并记下了途中留宿过的城市的评级总和；
”$QMxy$”：一位旅行者从城市$x$出发，到城市$y$，并记下了途中留宿过
的城市的评级最大值。
由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。 为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。

Input

输入的第一行包含整数$N，Q$依次表示城市数和事件数。
接下来N行，第i+l行两个整数 W i ， C i W_i，C_i 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 < = 1 0 5 ， C < = 1 0 5 N，Q < =10^5 ， C < =10^5 N，Q<=105，C<=105

数据保证对所有$QS$和$QM$事件，起点和终点城市的信仰相同；在任意时

刻，城市的评级总是不大于 1 0 4 10^4 104的正整数，且宗教值不大于$C$。

Source

$Round1Day1$

题意：

给你一颗无根树，每个节点代表一座城市，每座城市信仰的宗教 为 C i C_i Ci​，城市评级 W i W_i Wi​ ,实现如下操作：

• 修改城市$x$的评级
• 修改城市$x$的信仰
• 查询从城市$x$到城市$y$的最短路径上的所有信仰宗教 C y C_y Cy​的城市的评级最大值
• 查询从城市$x$到城市$y$的最短路径上的所有信仰宗教 C y C_y Cy​的城市的评级之和

题解

• 1A还是很舒服的233
• 因为最多1e5种宗教，可以考虑先树剖出每个节点编号，然后对于每个宗教，用一颗线段树（动态开点）维护这个宗教所在的所有城市对应的树剖出来的下标，这样就可以完成对于亮点之间特定的宗教对应的最大值以及和，复杂度$n\log n$（但是如果是要求两点间所有节点评级和呢？暂时只知道 n 2 n^2 n2 $\log n$的做法，即枚举一下所有两点之间的城市信仰，然后对每一个信仰再去更新）

附代码

#includeusing 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));}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！