自动搬运

查看原文

来自洛谷，原作者为

	kraylas **

搬运于2025-08-24 22:02:42，当前版本为作者最后更新于2019-04-03 18:48:21，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

对于树上所有路径的问题显然可以点分治

但是点分治难写怎么办

因为是每次从一个点出发，所以可以想到LCT

考虑如何用LCT维护这个东西

因为是一个点的权值减去一条链的权值

所以可以在splay上维护从splay最左边和最右边（因为要翻转）到某一个点的答案最大值

但当前点到其他点显然不是只有一条链

只有一条链的splay好像并不能很好维护这个东西

所以考虑维护虚边

因为一个点的虚边有好多，而且我们要求最大值，而且要支持删除，用set可以很好维护

所以第一步的思路就出来了:

• 拆边为点，维护边权和点权(一个点边权为0，一个边点权为-inf)
• 维护splay上从最左边开始到这条链以及所有虚边链接的点的最优答案，和从右开始的最优答案

一个节点维护三个权值表示边权，点权，splay上这个点子树的边权和

再维护两个最大值表示从左和从右的最优答案

struct Node{
	Node  *ch[2],*fa;
    int64 pval,eval,sum; //点权，边权，边权和
    Value lmax,rmax;     //左右答案
    set<Value> imax;     //虚边
};

然后考虑怎样合并这些信息（也就是push_up）

先考虑sum

很显然sum就是左右两子树的sum之和加上自己的边权

然后是lmax

分为四部分

1. 左边的lmax
2. 左边的sum+自己的边权+虚边上的最大值
3. 左边的sum+自己边权+右子树最大值
4. 左边的sum+自己点权

rmax同理

所以up函数也可以写出来了

void up(ptr x){
	x->sum=x->eval+x->ch[0]->sum+x->ch[1]->sum;
	Value imax=x->imax.size()? *x->imax.rbegin():Value(-inf,0);
	x->lmax=max(x->ch[0]->lmax,x->ch[0]->sum+
				max(
					x->eval+max(imax,x->ch[1]->lmax),
					Value(x->pval,x-pool)
				)
			);
	x->rmax=max(x->ch[1]->rmax,x->ch[1]->sum+
				max(
					x->eval+max(imax,x->ch[0]->rmax),
					Value(x->pval,x-pool)
				)
			);
}

然后就是LCT板子了，注意access的时候把虚边维护好就可以了

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
template<class T> T read(){
	T s,f=1;char ch;
	while(!isdigit(ch=getchar()))(ch=='-')&&(f=-1);
	for(s=ch-'0';isdigit(ch=getchar());s=s*10+ch-'0');
	return s*f;
}
namespace cmp{
template<class T> bool chkmax(T &a,const T &b){return a<b? a=b,1:0;}
template<class T> bool chkmin(T &a,const T &b){return b<a? a=b,1:0;}
}
const int maxn = 1e5+5;
const long long inf = 1LL<<62;
typedef long long int64;


int (*_)()=read<int>;

struct Value{
	int64 val;
	int id;
	Value(int64 val=0,int id=0):val(val),id(id){}
	friend bool operator < (const Value &a,const Value &b){
		return a.val==b.val? a.id>b.id:a.val<b.val;
	}
	friend Value operator + (const int64 &a,const Value &b){
		return Value(b.val+a,b.id);
	}
};


struct Node{
	Node *ch[2],*fa;
	int64 pval,eval,sum;
	Value lmax,rmax;
	bool rev;
	set<Value> imax;
}pool[maxn*2];
typedef Node *ptr;
ptr null=&pool[0];

Node *Nodeinit(Node *p){
	p->ch[0]=p->ch[1]=null;
	p->fa=null;
	p->pval=p->eval=p->sum=0;
	p->lmax=p->rmax=Value(0,0);
	p->rev=0;
	p->imax.clear();
	return p;
}

bool ntr(ptr x){return x->fa->ch[0]==x||x->fa->ch[1]==x;}
bool getd(ptr x){return x->fa->ch[1]==x;}
void up(ptr x){
	x->sum=x->eval+x->ch[0]->sum+x->ch[1]->sum;
	Value imax=x->imax.size()? *x->imax.rbegin():Value(-inf,0);
	x->lmax=max(x->ch[0]->lmax,x->ch[0]->sum+
				max(
					x->eval+max(imax,x->ch[1]->lmax),
					Value(x->pval,x-pool)
				)
			);
	x->rmax=max(x->ch[1]->rmax,x->ch[1]->sum+
				max(
					x->eval+max(imax,x->ch[0]->rmax),
					Value(x->pval,x-pool)
				)
			);
}

void r(ptr p){
	swap(p->ch[0],p->ch[1]);
	swap(p->lmax,p->rmax);
	p->rev^=1;
}

void down(ptr x){
	if(!x->rev)return ;
	if(x->ch[0]!=null) r(x->ch[0]);
	if(x->ch[1]!=null) r(x->ch[1]);
	x->rev=0;
}

void rot(ptr x){
	ptr y=x->fa,z=y->fa;int k=getd(x);ptr w=x->ch[!k];
	if(ntr(y))z->ch[getd(y)]=x;
	x->fa=z;y->fa=x;x->ch[!k]=y;y->ch[k]=w;
	if(w!=null) w->fa=y;
	up(y);
}

void splay(ptr x){
	static ptr st[maxn];
	int top;st[top=1]=x;
	while(ntr(st[top])) st[top+1]=st[top]->fa,top++;
	while(top)down(st[top--]);
	for(;ntr(x);rot(x))
		if(ntr(x->fa)) rot(getd(x->fa)==getd(x)? x->fa:x);
	up(x);
}

void access(ptr x){
	for(ptr y=null;x!=null;x=(y=x)->fa){
		splay(x);
		if(y!=null)
			x->imax.erase(y->lmax);
		if(x->ch[1]!=null)
			x->imax.insert(x->ch[1]->lmax);
		x->ch[1]=y;
		up(x);
	}
}

void makeroot(ptr x){
	access(x);
	splay(x);
	r(x);
}

void link(ptr x,ptr f){
	makeroot(x);
	access(f);
	splay(f);
	x->fa=f;
	f->imax.insert(x->lmax);
	up(f);
}

unordered_map<int64,int>edge;
int64 encode(int x,int y){if(x>y)swap(x,y); return (1LL*x)<<32|y; }
int n,m,q;
int main(){
	Nodeinit(null);
	null->lmax=null->rmax=Value(-inf,n+1);
	null->sum=0;
	n=_();q=_();
	for(int i=1;i<n*2;++i)
		Nodeinit(pool+i);
	for(int i=1;i<=n;++i)
		pool[i].pval=read<int64>(),up(pool+i);
	for(int i=1;i<n;++i){
		int x=_(),y=_();
		int64 z=read<int64>();
		pool[i+n].eval=-z;
		pool[i+n].pval=-inf;
		link(pool+x,pool+i+n);
		link(pool+y,pool+i+n);
		edge[encode(x,y)]=i;
	}
	makeroot(pool+1);
	int nowpos=1;
	for(int i=1;i<=q;++i){
		int op=_();
		if(op==1){
			int x=_();
			int64 z=read<int64>();
			access(pool+x);
			splay(pool+x);
			pool[x].pval=z;
			up(pool+x);
		}else{
			int x=_(),y=_();
			int64 z=read<int64>();
			int id=edge[encode(x,y)]+n;
			access(pool+id);
			splay(pool+id);
			pool[id].eval=-z;
			up(pool+id);
		}
		access(pool+nowpos);
		splay(pool+nowpos);

		int64 tmp=pool[nowpos].pval;
		pool[nowpos].pval=-inf;
		up(pool+nowpos);

		int ans=pool[nowpos].lmax.id;
		pool[nowpos].pval=tmp;
		up(pool+nowpos);

		nowpos=ans;
		makeroot(pool+nowpos);
		printf("%d%c",nowpos,i==q? '\n':' ');
	}
	return 0;
}

让我们一起膜拜大佬olinr