https://www.luogu.org/problem/P4114
维护边权的话，用深度大的点表示这条边（可以遍历一边边询问两端深度，这样不需要修改dfs1，也可以在dfs1的时候向下走的同时把边权拷贝进深度大的点。），然后在链上问的时候，最后一次问的左端点要+1（小心左右端点原本重合）。
要注意每个点x实际上在线段树上的位置是tid[x]，不要改错了。线段树build的时候初始化的不是a[x]而是a[rnk[x]]，也就是x号线段树位置对应的dfn序，也就是节点本身（rnk和tid互为逆运算）。
#include<bits/stdc++.h>
#define lc (o<<1)
#define rc (o<<1|1)
typedef long long ll;
using namespace std;
const ll INF = 1e18;
const int MAXN = 100000 + 5;
int dep[MAXN], siz[MAXN], son[MAXN], fa[MAXN], top[MAXN], tid[MAXN], rnk[MAXN], cnt;
int n, m;
int head[MAXN], etop;
struct Edge {
int v, w, next;
} e[MAXN * 2];
inline void init(int n) {
etop = 0;
memset(head, -1, sizeof(head[0]) * (n + 1));
}
inline void addedge(int u, int v, int w) {
e[++etop].v = v;
e[etop].w = w;
e[etop].next = head[u];
head[u] = etop;
e[++etop].v = u;
e[etop].w = w;
e[etop].next = head[v];
head[v] = etop;
}
int a[MAXN];
struct SegmentTree {
int ma[MAXN * 4];
void build(int o, int l, int r) {
if(l == r) {
ma[o] = a[rnk[l]];
} else {
int m = (l + r) >> 1;
build(lc, l, m);
build(rc, m + 1, r);
pushup(o);
}
}
void pushup(int o) {
ma[o] = max(ma[lc], ma[rc]);
}
void update(int o, int l, int r, int x, int v) {
if(l == r) {
ma[o] = v;
} else {
int m = (l + r) >> 1;
if(x <= m)
update(lc, l, m, x, v);
if(x >= m + 1)
update(rc, m + 1, r, x, v);
pushup(o);
}
}
ll querymax(int o, int l, int r, int ql, int qr) {
if(ql <= l && r <= qr) {
return ma[o];
} else {
int m = (l + r) >> 1;
ll res = -INF;
if(ql <= m)
res = max(res, querymax(lc, l, m, ql, qr));
if(qr >= m + 1)
res = max(res, querymax(rc, m + 1, r, ql, qr));
return res;
}
}
} st;
void init1() {
dep[1] = 1;
}
void dfs1(int u, int t) {
siz[u] = 1, son[u] = -1, fa[u] = t;
for(int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if(v == t)
continue;
dep[v] = dep[u] + 1;
a[v]=e[i].w;
dfs1(v, u);
siz[u] += siz[v];
if(son[u] == -1 || siz[v] > siz[son[u]])
son[u] = v;
}
}
void init2() {
cnt = 0;
}
void dfs2(int u, int t) {
top[u] = t;
tid[u] = ++cnt;
rnk[cnt] = u;
if(son[u] == -1)
return;
dfs2(son[u], t);
for(int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if(v == fa[u] || v == son[u])
continue;
dfs2(v, v);
}
}
ll querymax1(int u, int v) {
if(u == v)
return 0;
ll ret = -INF;
for(int tu = top[u], tv = top[v]; tu != tv; u = fa[tu], tu = top[u]) {
if(dep[tu] < dep[tv])
swap(u, v), swap(tu, tv);
ret = max(ret, st.querymax(1, 1, n, tid[tu], tid[u]));
}
if(tid[u] == tid[v])
return ret;
if(dep[u] > dep[v])
swap(u, v);
ret = max(ret, st.querymax(1, 1, n, tid[u] + 1, tid[v]));
return ret;
}
void change() {
int i, val;
scanf("%d%d", &i, &val);
int u = e[2*i-1].v, v = e[2*i].v;
int x = u;
if(dep[v] > dep[u])
x = v;
st.update(1, 1, n, tid[x], val);
}
void query() {
int u, v;
scanf("%d%d", &u, &v);
ll res = querymax1(u, v);
printf("%lld\n", res);
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
scanf("%d", &n);
init(n);
for(int i = 1, u, v, w; i <= n - 1; ++i) {
scanf("%d%d%d", &u, &v, &w);
addedge(u, v, w);
}
init1(),dfs1(1, -1);
init2(),dfs2(1, 1);
st.build(1, 1, n);
char op[20];
while(~scanf("%s", op)) {
switch(op[0]) {
case 'C':
change();
break;
case 'Q':
query();
break;
case 'D':
return 0;
}
}
return 0;
}