P10659 BZOJ3159 决战
P10659 BZOJ3159 决战
Problem
给定一棵树，要求实现：
- 对某条路径上的所有节点点权加上
w 。 - 求某条路径上的点权和。
- 求某条路径上的点权最大值。
- 求某条路径上的点权最小值。
- 翻转某条路径上的点权。
Solution
这道题用 LCT 的通用性更强，不需要用到路径的性质。如果没有路径翻转，那么这道题就是 LCT 的模板题。下面只考虑翻转操作。
假设翻转路径的两端为
之后我们不能直接翻转这颗 splay，这意味着将这颗大树的根换成
此时可以对于大树上的每一颗 splay 树开一个 dfs 序对应的权值 splay。这样子翻转操作就只用在 split 后翻转
只是 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;
}