自动搬运

查看原文

来自洛谷，原作者为

	xzz_cat6 all in出奇迹

搬运于2025-08-24 23:00:01，当前版本为作者最后更新于2025-03-16 15:05:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P10659 BZOJ3159 决战

Problem

给定一棵树，要求实现：

• 对某条路径上的所有节点点权加上 $w$。
• 求某条路径上的点权和。
• 求某条路径上的点权最大值。
• 求某条路径上的点权最小值。
• 翻转某条路径上的点权。

Solution

这道题用 LCT 的通用性更强，不需要用到路径的性质。如果没有路径翻转，那么这道题就是 LCT 的模板题。下面只考虑翻转操作。

假设翻转路径的两端为 $x$ 和 $y$。则先按照套路将 $x$ 和 $y$ 进行 split 操作，此时这条路径构成一个 splay 树。且位于整棵树的树根部，$x$ 为这颗大树的根。

之后我们不能直接翻转这颗 splay，这意味着将这颗大树的根换成 $y$，没有实质作用。我们希望的是在不改变树的形态的情况下翻转权值，那么我们不妨将权值单开一个数据结构维护。

此时可以对于大树上的每一颗 splay 树开一个 dfs 序对应的权值 splay。这样子翻转操作就只用在 split 后翻转 $x$ 所在的 splay 对应的权值 splay 即可。对于 access 操作，可以给每个点维护它所在的 splay 对应的权值 splay 的根，两棵树同步维护，断开右儿子的时候按照对应的排名断开权值树的右儿子。对于 makeroot 中的翻转操作，只需将对应的权值树翻转，保证 dfs 序相同。对于其他操作，都是基于 access 和 makeroot 操作的，无需改变权值树形态。查询操作直接查对应的权值树即可得到答案。

只是 access 操作变了一点，代码基本套模板，就是维护的东西多了一些。

Code

#include<bits/stdc++.h>
#define N 50005
#define int long long 
using namespace std;
int n,m,rt;
vector<int> e[N];
#define ls(u) (ch[u][0])
#define rs(u) (ch[u][1])
namespace T1{
	int ch[N][2],fa[N],tag[N],tag2[N];
	int mn[N],mx[N],val[N],sum[N],siz[N];
	bool get(int u){
		return rs(fa[u])==u;
	}
	bool isroot(int u){
		return ls(fa[u])!=u&&rs(fa[u])!=u;
	}
	void pushup(int u){
		mn[u]=val[u],mx[u]=val[u];
		if(ls(u)){
			mn[u]=min(mn[u],mn[ls(u)]);
			mx[u]=max(mx[u],mx[ls(u)]);
		}
		if(rs(u)){
			mn[u]=min(mn[u],mn[rs(u)]);
			mx[u]=max(mx[u],mx[rs(u)]);
		}
		siz[u]=siz[ls(u)]+siz[rs(u)]+1;
		sum[u]=sum[ls(u)]+sum[rs(u)]+val[u];
	}
	void pushrev(int u){
		swap(ls(u),rs(u));
		tag[u]^=1;
	}
	void pushrev(int u,int x){
		mx[u]+=x,mn[u]+=x,val[u]+=x,sum[u]+=siz[u]*x,tag2[u]+=x;
	}
	void pushdown(int u){
		if(tag[u]){
			if(ls(u))	pushrev(ls(u));
			if(rs(u))	pushrev(rs(u));
			tag[u]^=1;
		}
		if(tag2[u]){
			if(ls(u))	pushrev(ls(u),tag2[u]);
			if(rs(u))	pushrev(rs(u),tag2[u]);
			tag2[u]=0;
		}
	}
	void update(int u){
		if(!isroot(u))	update(fa[u]);
		pushdown(u);
	}
	void rotate(int x){
		int y=fa[x],z=fa[y],f=get(x);
		if(!isroot(y))	ch[z][get(y)]=x;
		ch[y][f]=ch[x][f^1];
		if(ch[x][f^1])	fa[ch[x][f^1]]=y;
		ch[x][f^1]=y,fa[y]=x,fa[x]=z;
		pushup(y),pushup(x);
	}
	void splay(int x){
		update(x);
		for(int f=fa[x];!isroot(x);rotate(x),f=fa[x]){
			if(!isroot(f))	rotate(get(x)==get(f)?f:x);
		}
	}
	int kth(int x,int k){
		while(1){
			pushdown(x);
			if(siz[ls(x)]+1==k){
				splay(x);
				return x;
			}
			if(siz[ls(x)]>=k)	x=ls(x);
			else	k-=siz[ls(x)]+1,x=rs(x);
		}
	}
	
	void print(){
		for(int i=1;i<=n;i++){
			cout<<ls(i)<<' '<<rs(i)<<' '<<fa[i]<<' '<<siz[i]<<' '<<mn[i]<<' '<<mx[i]<<' '<<val[i]<<' '<<sum[i]<<' '<<tag[i]<<' '<<tag2[i]<<'\n';
		} 
	}
}
namespace T2{
	int ch[N][2],fa[N],tag[N],siz[N],pos[N],tag2[N];
	void print(){
		for(int i=1;i<=n;i++){
			cout<<ls(i)<<' '<<rs(i)<<' '<<fa[i]<<' '<<siz[i]<<' '<<pos[i]<<' '<<tag[i]<<' '<<tag2[i]<<'\n';
		} 
	}
	bool get(int u){
		return rs(fa[u])==u;
	}
	bool isroot(int u){
		return ls(fa[u])!=u&&rs(fa[u])!=u;
	}
	void pushup(int u){
		siz[u]=siz[ls(u)]+siz[rs(u)]+1; 
	}
	void pushrev(int u){
		swap(ls(u),rs(u));
		tag[u]^=1;
	}
	void pushrev(int u,int x){
		if(!u)	return;
		pos[u]=tag2[u]=x;
	}
	void pushdown(int u){
		if(tag[u]){
			if(ls(u))	pushrev(ls(u));
			if(rs(u))	pushrev(rs(u));
			tag[u]^=1;
		}
		if(tag2[u]){
			if(ls(u))	pushrev(ls(u),tag2[u]);
			if(rs(u))	pushrev(rs(u),tag2[u]);
			tag2[u]=0;
		}
	}
	void update(int u){
		if(!isroot(u))	update(fa[u]);
		pushdown(u);
	}
	void rotate(int x){
		int y=fa[x],z=fa[y],f=get(x);
		if(!isroot(y))	ch[z][get(y)]=x;
		ch[y][f]=ch[x][f^1];
		if(ch[x][f^1])	fa[ch[x][f^1]]=y;
		ch[x][f^1]=y,fa[y]=x,fa[x]=z;
		pushup(y),pushup(x);
	}
	void splay(int x){
		update(x);
		for(int f=fa[x];!isroot(x);rotate(x),f=fa[x]){
			if(!isroot(f))	rotate(get(x)==get(f)?f:x);
		}
	}
	void access(int x1){
		splay(x1);
		int u1=0,x2,u2=0;
		while(x1){
			splay(x1),T1::splay(pos[x1]),x2=T1::kth(pos[x1],siz[ls(x1)]+1);
			if(rs(x1))	pushrev(rs(x1),T1::ch[x2][1]);
			rs(x1)=u1,T1::ch[x2][1]=u2;
			if(u2)	T1::fa[u2]=x2;
			pushrev(x1,x2);
			pushup(x1),u1=x1,x1=fa[x1];
			T1::pushup(x2),u2=x2;
		}
	}
	void makeroot(int x){
		access(x),splay(x);
		pushrev(x),T1::pushrev(pos[x]);
	}
	void split(int x,int y){
		makeroot(x),access(y),splay(y);
	}
	void add(int x,int y,int z){
		split(x,y),T1::pushrev(pos[y],z);
	}
	void modify(int x,int y){
		split(x,y),T1::pushrev(pos[y]);
	}
	int qmin(int x,int y){
		return split(x,y),T1::mn[pos[y]];
	}
	int qmax(int x,int y){
		return split(x,y),T1::mx[pos[y]];
	}
	int query(int x,int y){
		return split(x,y),T1::sum[pos[y]];
	}
}
void dfs(int u,int f){
	T2::pos[u]=u,T2::siz[u]=1,T1::siz[u]=1;
	if(f)	T1::fa[u]=f,T2::fa[u]=f;
	for(auto v:e[u]){
		if(v==f)	continue;
		dfs(v,u);
	}
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>rt;
	for(int i=1,x,y;i<n;i++){
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}dfs(rt,0);
	for(int i=1;i<=m;i++){
		string s;
		int x,y,z;
		cin>>s>>x>>y;
		switch(s[2]){
			case 'm':{
				cout<<T2::query(x,y)<<'\n';
				break;
			}
			case 'c':{
				cin>>z,T2::add(x,y,z);
				break;
			}
			case 'n':{
				cout<<T2::qmin(x,y)<<'\n';
				break;
			}
			case 'j':{
				cout<<T2::qmax(x,y)<<'\n';
				break;
			}
			case 'v':{
				T2::modify(x,y);
				break;
			}
		}
	}
	return 0;
}