rt，悬一关

code

#include<bits/stdc++.h>
#define lson (p << 1)
#define rson (p << 1 | 1)
using namespace std;
const int N = 1e5 + 5,INF = 2e9;
int n;
string op;
struct node{
	int v,w;
};
vector<node> adj[N];
int top[N],fa[N],dep[N],son[N],siz[N],a[N],id[N],w[N],cnt = 0;
inline void dfs_1(int u,int fat)
{
	fa[u] = fat,siz[u] = 1,son[u] = 0,dep[u] = dep[fat] + 1;
	for(auto e : adj[u])
	{
		if(e.v == fat) continue;
		a[e.v] = e.w;
		dfs_1(e.v,u);
		siz[u] += siz[e.v];
		if(siz[e.v] > siz[son[u]]) son[u] = e.v;
	}
}
inline void dfs_2(int u,int tp)
{
	top[u] = tp;
	id[u] = ++cnt;
	w[cnt] = a[u];
	if(!son[u]) return;
	dfs_2(son[u],tp);
	for(auto e : adj[u])
	{
		if(e.v != fa[u] && e.v != son[u]) dfs_2(e.v,e.v);
	}
}
struct tree
{
	struct node
	{
		int l,r;
		int mx;
		int lz1,lz2;//1：覆盖，2：加 
	}tr[N << 2];
	inline void push_down_1(int p)
	{
		if(tr[p].lz1 != -INF)
		{
			tr[lson].lz2 = tr[rson].lz2 = 0;
			tr[lson].mx = tr[rson].mx = tr[p].lz1;
			tr[lson].lz1 = tr[rson].lz1 = tr[p].lz1;
			tr[p].lz1 = -INF;
		}
	}
	inline void push_down_2(int p)
	{
		if(tr[p].lz2)
		{
			tr[lson].mx += tr[p].lz2,tr[rson].mx += tr[p].lz2;
			tr[lson].lz2 += tr[p].lz2,tr[rson].lz2 += tr[p].lz2;
			tr[p].lz2 = 0;
		}
	}
	inline void push_down(int p)
	{
		push_down_1(p),push_down_2(p);
	}
	inline void push_up(int p)
	{
		tr[p].mx = max(tr[lson].mx,tr[rson].mx);
	}
	inline void build(int p,int l,int r)
	{
		tr[p] = {l,r,0,-INF,0};
		if(l == r)
		{
			tr[p].mx = w[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(lson,l,mid),build(rson,mid + 1,r);
		push_up(p);
	}
	inline void modify_1(int p,int l,int r,int k)
	{
		if(l <= tr[p].l && tr[p].r <= r)
		{
			tr[p].lz1 = k;
			tr[p].mx = k;
			tr[p].lz2 = 0;
			return;
		}
		push_down(p);
		if(l <= tr[lson].r) modify_1(lson,l,r,k);
		if(r >= tr[rson].l) modify_1(rson,l,r,k);
		push_up(p);
	}
	inline void modify_2(int p,int l,int r,int k)
	{
		if(l <= tr[p].l && tr[p].r <= r)
		{
			push_down_1(p);
			tr[p].lz2 += k,tr[p].mx += k;
			return;
		}
		push_down(p);
		if(l <= tr[lson].r) modify_2(lson,l,r,k);
		if(r >= tr[rson].l) modify_2(rson,l,r,k);
		push_up(p);
	}
	inline int query(int p,int l,int r)
	{
		if(l <= tr[p].l && tr[p].r <= r) return tr[p].mx;
		push_down(p);
		int ans = -INF;
		if(l <= tr[lson].r) ans = max(ans,query(lson,l,r));
		if(r >= tr[rson].l) ans = max(ans,query(rson,l,r));
		return ans;
	}
}tr;
inline void modify_1(int k,int w)
{
	tr.modify_1(1,id[k],id[k],w);
}
inline void modify_2(int u,int v,int w)
{
	while(top[u] != top[v])
	{
		if(dep[top[u]] < dep[top[v]]) swap(u,v);
		tr.modify_1(1,id[top[u]],id[u],w);
		u = fa[top[u]];
	}
	if(dep[u] > dep[v]) swap(u,v);
	tr.modify_1(1,id[u],id[v],w);
}
inline void modify_3(int u,int v,int w)
{
	while(top[u] != top[v])
	{
		if(dep[top[u]] < dep[top[v]]) swap(u,v);
		tr.modify_2(1,id[top[u]],id[u],w);
		u = fa[top[u]];
	}
	if(dep[u] > dep[v]) swap(u,v);
	tr.modify_2(1,id[u],id[v],w);
}
inline int query(int u,int v)
{
	int res = -INF;
	while(top[u] != top[v])
	{
		if(dep[top[u]] < dep[top[v]]) swap(u,v);
		res = max(res,tr.query(1,id[top[u]],id[u]));
		u = fa[top[u]];
	}
	if(dep[u] > dep[v]) swap(u,v);
	res = max(res,tr.query(1,id[u],id[v]));
	return res;
}
int main()
{
	//freopen("P4315_1.in","r",stdin);
	//freopen("P4315.txt","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n;
	for(int i = 1,u,v,w;i < n;i++)
	{
		cin >> u >> v >> w;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	}
	dfs_1(1,0),dfs_2(1,1);
	tr.build(1,1,n);
	while(cin >> op && op != "Stop")
	{
		if(op == "Change")
		{
			int k,w;
			cin >> k >> w;
			modify_1(k,w);
		}
		if(op == "Cover")
		{
			int u,v,w;
			cin >> u >> v >> w;
			modify_2(u,v,w);
		}
		if(op == "Add")
		{
			int u,v,w;
			cin >> u >> v >> w;
			modify_3(u,v,w);
		}
		if(op == "Max")
		{
			int u,v;
			cin >> u >> v;
			cout << query(u,v) << "\n";
		}
	}
}