P4315月下毛景树

#include <iostream>
using namespace std;
#define MAXN 300005
#define lson (x<<1)
#define rson (x<<1|1)
struct node {
	int u, v, w ;
} g[MAXN];
struct segm {
	int l, r, add, chn, maxq, minq, sum ;
} seg[MAXN];
int first[MAXN], nxt[MAXN], cntt = 0 ;
int fa[MAXN], dep[MAXN], son[MAXN], size[MAXN] ;
int top[MAXN], id[MAXN], rk[MAXN], cnt = 0 ;
int a[MAXN], n ;
void push(int u, int v, int w) {
	g[++cntt].u = u ;
	g[cntt].v = v ;
	g[cntt].w = w ;
	nxt[cntt] = first[u] ;
	first[u] = cntt ;
}
void dfs1(int x, int d, int f) {
	fa[x] = f ;
	dep[x] = d ;
	size[x] = 1 ;
	son[x] = 0 ;
	for(int i = first[x]; i; i = nxt[i]) {
		int tmp = g[i].v ;
		if(tmp != f) {
			dfs1(tmp, d + 1, x) ;
			if(size[tmp] > size[son[x]])
				son[x] = tmp ;
			size[x] += size[tmp] ;
		}
	}
}
void dfs2(int x, int t) {
	top[x] = t ;
	id[x] = ++cnt ;
	rk[cnt] = x ;
	if(!son[x]) return ;
	dfs2(son[x], t) ;
	for(int i = first[x]; i; i = nxt[i]) {
		int tmp = g[i].v ;
		if((tmp != fa[x]) && (tmp != son[x])) //!!!=son[x]
			dfs2(tmp, tmp) ;
	}
}
void build(int x, int l, int r) {
	seg[x].l = l ;
	seg[x].r = r ;
	if(l == r) {
		seg[x].sum = a[rk[l]] ;
		seg[x].add = seg[x].chn = 0 ;
		seg[x].maxq = seg[x].minq = a[rk[l]] ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	build(lson, l, mid) ;
	build(rson, mid + 1, r) ;
	seg[x].sum = seg[lson].sum + seg[rson].sum ;
	seg[x].maxq = max(seg[lson].maxq, seg[rson].maxq) ;
	seg[x].minq = min(seg[lson].minq, seg[rson].minq) ;
}
void pushdown(int x) {
	if(seg[x].chn) {
		seg[lson].chn = seg[rson].chn = seg[x].chn ;
		seg[lson].add = seg[rson].add = 0 ;
		seg[lson].sum = (seg[lson].r - seg[lson].l + 1) * seg[x].chn ;
		seg[rson].sum = (seg[rson].r - seg[rson].l + 1) * seg[x].chn ;
		seg[lson].maxq = seg[rson].maxq =
		                     seg[lson].minq = seg[rson].minq = seg[x].chn ;
		seg[x].chn = 0 ;
	}
	if(seg[x].add) {
		seg[lson].add += seg[x].add ;
		seg[rson].add += seg[x].add ;
		seg[lson].sum += (seg[lson].r - seg[lson].l + 1) * seg[x].add ;
		seg[rson].sum += (seg[rson].r - seg[rson].l + 1) * seg[x].add ;
		seg[lson].maxq += seg[x].add ;
		seg[rson].maxq += seg[x].add ;
		seg[lson].minq += seg[x].add ;
		seg[rson].minq += seg[x].add ;
		seg[x].add = 0 ;
	}
}
void update(int x, int l, int r, int d) {
	if(l <= seg[x].l && seg[x].r <= r) {
		seg[x].add += d ;
		seg[x].maxq += d ;
		seg[x].minq += d ;
		seg[x].sum += (seg[x].r - seg[x].l + 1) * d ;
		return ;
	}
	pushdown(x) ;
	int mid = (seg[x].l + seg[x].r) >> 1 ;
	if(l <= mid) update(lson, l, r, d) ;
	if(mid < r) update(rson, l, r, d) ;
	seg[x].sum = seg[lson].sum + seg[rson].sum ;
	seg[x].maxq = max(seg[lson].maxq, seg[rson].maxq) ;
	seg[x].minq = min(seg[lson].minq, seg[rson].minq) ;
}
void change(int x, int l, int r, int d) {
	if(l <= seg[x].l && seg[x].r <= r) {
		seg[x].add = 0 ;
		seg[x].chn = d ;
		seg[x].maxq = d ;
		seg[x].minq = d ;
		seg[x].sum = (seg[x].r - seg[x].l + 1) * d ;
		return ;
	}
	pushdown(x) ;
	int mid = (seg[x].l + seg[x].r) >> 1 ;
	if(l <= mid) change(lson, l, r, d) ;
	if(mid < r) change(rson, l, r, d) ;
	seg[x].sum = seg[lson].sum + seg[rson].sum ;
	seg[x].maxq = max(seg[lson].maxq, seg[rson].maxq) ;
	seg[x].minq = min(seg[lson].minq, seg[rson].minq) ;
}
int query(int x, int l, int r) {
	if(l <= seg[x].l && seg[x].r <= r)
		return seg[x].sum ;
	pushdown(x) ;
	int mid = (seg[x].l + seg[x].r) >> 1 ;
	int ans = 0 ;
	if(l <= mid) ans += query(lson, l, r) ;
	if(mid < r) ans += query(rson, l, r) ;
	return ans ;
}
int querymax(int x, int l, int r) {
	if(l <= seg[x].l && seg[x].r <= r)
		return seg[x].maxq ;
	pushdown(x) ;
	int mid = (seg[x].l + seg[x].r) >> 1 ;
	int ans = -0x3f3f3f3f ;
	if(l <= mid) ans = max(ans, querymax(lson, l, r)) ;
	if(mid < r) ans = max(ans, querymax(rson, l, r)) ;
	return ans ;
}
int querymin(int x, int l, int r) {
	if(l <= seg[x].l && seg[x].r <= r)
		return seg[x].minq ;
	pushdown(x) ;
	int mid = (seg[x].l + seg[x].r) >> 1 ;
	int ans = 0x3f3f3f3f ;
	if(l <= mid) ans = min(ans, querymin(lson, l, r)) ;
	if(mid < r) ans = min(ans, querymin(rson, l, r)) ;
	return ans ;
}
void updatepath(int x, int y, int d) {
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) swap(x, y) ;
		update(1, id[top[x]], id[x], d) ;
		x = fa[top[x]] ;
	}
	if(dep[x] > dep[y]) swap(x, y) ;
	update(1, id[x] + 1, id[y], d) ;
}
void changepath(int x, int y, int d) {
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) swap(x, y) ;
		change(1, id[top[x]], id[x], d) ;
		x = fa[top[x]] ;
	}
	if(dep[x] > dep[y]) swap(x, y) ;
	change(1, id[x] + 1, id[y], d) ;
}
int querypath(int x, int y) {
	int ans = 0 ;
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) swap(x, y) ;
		ans += query(1, id[top[x]], id[x]) ;
		x = fa[top[x]] ;
	}
	if(dep[x] > dep[y]) swap(x, y) ;
	ans += query(1, id[x] + 1, id[y]) ;
	return ans ;
}
int querypathmax(int x, int y) {
	int ans = -0x3f3f3f3f ;
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) swap(x, y) ;
		ans = max(ans, querymax(1, id[top[x]], id[x])) ;
		x = fa[top[x]] ;
	}
	if(dep[x] > dep[y]) swap(x, y) ;
	ans = max(ans, querymax(1, id[x] + 1, id[y])) ;
	return ans ;
}
int querypathmin(int x, int y) {
	int ans = 0x3f3f3f3f ;
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]]) swap(x, y) ;
		ans = min(ans, querymin(1, id[top[x]], id[x])) ;
		x = fa[top[x]] ;
	}
	if(dep[x] > dep[y]) swap(x, y) ;
	ans = min(ans, querymin(1, id[x] + 1, id[y])) ;
	return ans ;
}
void updatetree(int x, int d) {
	update(1, id[x], id[x] + size[x] - 1, d) ;
}
void changetree(int x, int d) {
	change(1, id[x], id[x] + size[x] - 1, d) ;
}
int querytree(int x) {
	return query(1, id[x], id[x] + size[x] - 1) ;
}
int querytreemax(int x) {
	return querymax(1, id[x], id[x] + size[x] - 1) ;
}
int querytreemin(int x) {
	return querymin(1, id[x], id[x] + size[x] - 1) ;
}
void findroot(int x, int f) {
	for(int i = first[x]; i; i = nxt[i]) {
		int tmp = g[i].v ;
		if(tmp != f) a[tmp] = g[i].w, findroot(tmp, x) ;
	}
}
int main() {
	cin >> n ;
	string com ;
	int u, v, w ;
	for(int i = 1; i < n; i++) {
		cin >> u >> v >> w ;
		push(u, v, w) ;
		push(v, u, w) ;
	}
	findroot(1, 0) ;
	dfs1(1, 1, 0) ;
	dfs2(1, 1) ;
	build(1, 1, n) ;
	while(cin >> com && com != "Stop") {
		if(com == "Change") {
			cin >> u >> v ;
			change(1, id[g[u].v], id[g[u].v], v) ;
		}
		if(com == "Cover") {
			cin >> u >> v >> w ;
			changepath(u, v, w) ;
		}
		if(com == "Add") {
			cin >> u >> v >> w ;
			updatepath(u, v, w) ;
		}
		if(com == "Max") {
			cin >> u >> v ;
			cout << querypathmax(u, v) << endl ;
		}
	}
	return 0 ;
}