线段树+树剖求调

#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define int long long
#define ls p<<1
#define rs p<<1|1
using namespace std;
const int N = 1e5 + 5, inf = 2e18;
struct edge
{
	int to, pre, val;
} e[N << 1];
int cnt, last[N];
void addedge(int u, int v, int w)
{
	e[++cnt].pre = last[u], e[cnt].to = v;
	e[cnt].val = w,last[u] = cnt;
}
int f[N], dep[N], siz[N], son[N], dfn[N], top[N], rnk[N], tot;
int a[N], st[N];
void dfs1(int u, int fa)
{
	f[u] = fa, dep[u] = dep[fa] + 1;
	siz[u] = 1;
	for (int i = last[u]; i; i = e[i].pre)
	{
		int v = e[i].to;
		if (v == fa)
		{
			continue;
		}
		a[v] = e[i].val;
		dfs1(v, u);
		siz[u] += siz[v];
		if (siz[son[u]] < siz[v])
		{
			son[u] = v;
		}
	}
}
void dfs2(int u, int t)
{
	dfn[u] = ++tot;
	top[u] = t;
	rnk[cnt] = u;
	if (son[u])
	{
		dfs2(son[u], t);
	}
	for (int i = last[u]; i; i = e[i].pre)
	{
		int v = e[i].to;
		if (v == f[u] || v == son[u])
		{
			continue;
		}
		dfs2(v, v);
	}
}
struct Node
{
	int l, r, maxx, tag, tag2;//tag为加法标记,tag2为覆盖标记 
} t[N << 2];
void push_up(int p)
{
	t[p].maxx = max(t[ls].maxx, t[rs].maxx);
}
void build(int p, int l, int r)
{
	t[p].l = l, t[p].r = r;
	t[p].tag2 = -inf;
	if (l == r)
	{
		t[p].maxx = a[rnk[l]];
		return;
	}
	int mid = (l + r) >> 1;
	build(ls, l, mid);
	build(rs, mid + 1, r);
	push_up(p);
}
void push_down(int p)
{
	if (t[p].tag2 != -inf)
	{
		t[rs].tag2 = t[p].tag2, t[rs].tag2 = t[p].tag2;
		t[ls].tag=t[rs].tag=0;
		t[ls].maxx = t[rs].maxx = t[p].tag2;
		t[p].tag2 = -inf;
	}
	if (t[p].tag)
	{
		t[ls].tag += t[p].tag, t[rs].tag += t[p].tag;
		t[ls].maxx += t[p].tag, t[rs].maxx += t[p].tag;
		t[p].tag = 0;
	}
}
void add(int p, int l, int r, int k)
{
	if (l <= t[p].l && r >= t[p].r)
	{
		t[p].maxx += k;
		t[p].tag += k;
		return;
	}
	int mid = (t[p].l + t[p].r) >> 1;
	push_down(p);
	if (l <= mid)
	{
		add(ls, l, r, k);
	}
	if (r > mid)
	{
		add(rs, l, r, k);
	}
	push_up(p);
}
void modify(int p, int l, int r, int k)
{
	if (l <= t[p].l && r >= t[p].r)
	{
		t[p].tag = 0;
		t[p].tag2 = t[p].maxx = k;
		return;
	}
	push_down(p);
	int mid = (t[p].l + t[p].r) >> 1;
	if (l <= mid)
	{
		modify(ls, l, r, k);
	}
	if (r > mid)
	{
		modify(rs, l, r, k);
	}
	push_up(p);
}
int askmax(int p, int l, int r)
{
	if (l <= t[p].l && r >= t[p].r)
	{
		return t[p].maxx;
	}
	push_down(p);
	int mid = (t[p].l + t[p].r) >> 1;
	int maxx = -inf;
	if (l <= mid)
	{
		maxx = max(maxx, askmax(ls, l, r));
	}
	if (r > mid)
	{
		maxx = max(maxx, askmax(rs, l, r));
	}
	return maxx;
}
int max_path(int x, int y)
{
	int maxx = -inf;
	while (top[x] != top[y])
	{
		if (dep[top[x]] < dep[top[y]])
		{
			swap(x, y);
		}
		maxx = max(maxx, askmax(1, dfn[top[x]], dfn[x]));
		x = f[top[x]];
	}
	if (dep[x] < dep[y])
	{
		swap(x, y);
	}
	maxx = max(maxx, askmax(1, dfn[y]+1, dfn[x]));
	return maxx;
}
void modify_path(int x, int y, int k)
{
	while (top[x] != top[y])
	{
		if (dep[top[x]] < dep[top[y]])
		{
			swap(x, y);
		}
		modify(1, dfn[top[x]], dfn[x], k);
		x = f[top[x]];
	}
	if (dep[x] < dep[y])
	{
		swap(x, y);
	}
	modify(1, dfn[y]+1, dfn[x], k);
}
void add_path(int x, int y, int k)
{
	while (top[x] != top[y])
	{
		if (dep[top[x]] < dep[top[y]])
		{
			swap(x, y);
		}
		add(1, dfn[top[x]], dfn[x], k);
		x = f[top[x]];
	}
	if (dep[x] < dep[y])
	{
		swap(x, y);
	}
	add(1, dfn[y] +1, dfn[x], k);
}
int u[N], v[N], w[N];
signed main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.ans","w",stdout);
	ios;
	int n;
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		cin >> u[i] >> v[i] >> w[i];
		addedge(u[i], v[i], w[i]);
		addedge(v[i], u[i], w[i]);
	}
	dfs1(1, 0);
	dfs2(1, 1);
	build(1, 1, n);
	for(int i=1; i<n; i++)
	{
		if(f[u[i]]==v[i])
		{
			st[i]=u[i];
		}
		else
		{
			st[i]=v[i];
		}
	}
	while (1)
	{
		string opt;
		cin >> opt;
		if (opt == "Stop")
		{
			break;
		}
		int l, r;
		cin >> l >> r;
		if (opt == "Change")
		{
			modify(1, dfn[st[l]],dfn[st[l]], r);
		}
		if (opt == "Cover")
		{
			int k;
			cin >> k;
			modify_path(l, r, k);
		}
		if (opt == "Add")
		{
			int k;
			cin >> k;
			add_path(l, r, k);
		}
		if (opt == "Max")
		{
			cout << max_path(l, r) << '\n';
		}
	}
	return 0;
}