题解
真真正正是个码农题，不过很套路，熟练就打得很快，不过要用点维护边的信息在 ( ext{LCA}) 出要注意，不能处理此点的信息
(Code)
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N = 2e5 + 5;
int n, m, h[N];
struct edge{int to, nxt, w, id;}e[N << 1];
inline void add(int u, int v, int w, int id)
{
static int tot = 0;
e[++tot] = edge{v, h[u], w, id}, h[u] = tot;
}
int top[N], fa[N], dfn[N], dep[N], siz[N], son[N], ver[N], edg[N];
void dfs1(int x)
{
siz[x] = 1;
for(register int i = h[x]; i; i = e[i].nxt)
{
int v = e[i].to;
if (v == fa[x]) continue;
edg[v] = e[i].w, ver[e[i].id] = v, fa[v] = x, dep[v] = dep[x] + 1, dfs1(v), siz[x] += siz[v];
if (siz[v] > siz[son[x]]) son[x] = v;
}
}
void dfs2(int x)
{
static int dfc = 0;
dfn[x] = ++dfc;
if (son[x]) top[son[x]] = top[x], dfs2(son[x]);
for(register int i = h[x]; i; i = e[i].nxt)
{
int v = e[i].to;
if (v == fa[x] || v == son[x]) continue;
top[v] = v, dfs2(v);
}
}
struct Tree{
#define ls (p << 1)
#define rs (ls | 1)
const int INF = 0x3f3f3f3f;
int sum[N << 2], mn[N << 2], mx[N << 2], tag[N << 2];
inline Tree(){memset(mn, 0x3f3f3f3f, sizeof mn), memset(mx, -0x3f3f3f3f, sizeof mx);}
void change(int p){sum[p] *= -1, mx[p] *= -1, mn[p] *= -1, swap(mx[p], mn[p]), tag[p] ^= 1;}
void pushup(int p){sum[p] = sum[ls] + sum[rs], mn[p] = min(mn[ls], mn[rs]), mx[p] = max(mx[ls], mx[rs]);}
void pushdown(int p)
{
if (!tag[p]) return;
change(ls), change(rs), tag[p] ^= 1;
}
void update_node(int p, int l, int r, int x, int v)
{
if (l == r)
{
sum[p] = mn[p] = mx[p] = v;
if (l == 1) mn[p] = INF, mx[p] = -INF;
return;
}
pushdown(p);
int mid = (l + r) >> 1;
if (x <= mid) update_node(ls, l, mid, x, v);
else update_node(rs, mid + 1, r, x, v);
pushup(p);
}
void update_rev(int p, int l, int r, int x, int y)
{
if (x <= l && r <= y) return void(change(p));
pushdown(p);
int mid = (l + r) >> 1;
if (x <= mid) update_rev(ls, l, mid, x, y);
if (y > mid) update_rev(rs, mid + 1, r, x, y);
pushup(p);
}
inline void tree_rev(int x, int y)
{
int fx = top[x], fy = top[y];
while (fx ^ fy)
{
if (dep[fx] > dep[fy]) update_rev(1, 1, n, dfn[fx], dfn[x]), x = fa[fx], fx = top[x];
else update_rev(1, 1, n, dfn[fy], dfn[y]), y = fa[fy], fy = top[y];
}
if (dep[x] > dep[y]) swap(x, y);
if (x == y) return;
update_rev(1, 1, n, dfn[x] + 1, dfn[y]);
}
int query_sum(int p, int l, int r, int x, int y)
{
if (x <= l && r <= y) return sum[p];
pushdown(p);
int mid = (l + r) >> 1, ret = 0;
if (x <= mid) ret += query_sum(ls, l, mid, x, y);
if (y > mid) ret += query_sum(rs, mid + 1, r, x, y);
return ret;
}
inline int tree_sum(int x, int y)
{
int fx = top[x], fy = top[y], ret = 0;
while (fx ^ fy)
{
if (dep[fx] > dep[fy]) ret += query_sum(1, 1, n, dfn[fx], dfn[x]), x = fa[fx], fx = top[x];
else ret += query_sum(1, 1, n, dfn[fy], dfn[y]), y = fa[fy], fy = top[y];
}
if (dep[x] > dep[y]) swap(x, y);
if (x == y) return ret;
return ret + query_sum(1, 1, n, dfn[x] + 1, dfn[y]);
}
int query_max(int p, int l, int r, int x, int y)
{
if (x <= l && r <= y) return mx[p];
pushdown(p);
int mid = (l + r) >> 1, ret = -INF;
if (x <= mid) ret = max(ret, query_max(ls, l, mid, x, y));
if (y > mid) ret = max(ret, query_max(rs, mid + 1, r, x, y));
return ret;
}
inline int tree_max(int x, int y)
{
int fx = top[x], fy = top[y], ret = -INF;
while (fx ^ fy)
{
if (dep[fx] > dep[fy]) ret = max(ret, query_max(1, 1, n, dfn[fx], dfn[x])), x = fa[fx], fx = top[x];
else ret = max(ret, query_max(1, 1, n, dfn[fy], dfn[y])), y = fa[fy], fy = top[y];
}
if (dep[x] > dep[y]) swap(x, y);
if (x == y) return ret;
return max(ret, query_max(1, 1, n, dfn[x] + 1, dfn[y]));
}
int query_min(int p, int l, int r, int x, int y)
{
if (x <= l && r <= y) return mn[p];
pushdown(p);
int mid = (l + r) >> 1, ret = INF;
if (x <= mid) ret = min(ret, query_min(ls, l, mid, x, y));
if (y > mid) ret = min(ret, query_min(rs, mid + 1, r, x, y));
return ret;
}
inline int tree_min(int x, int y)
{
int fx = top[x], fy = top[y], ret = INF;
while (fx ^ fy)
{
if (dep[fx] > dep[fy]) ret = min(ret, query_min(1, 1, n, dfn[fx], dfn[x])), x = fa[fx], fx = top[x];
else ret = min(ret, query_min(1, 1, n, dfn[fy], dfn[y])), y = fa[fy], fy = top[y];
}
if (dep[x] > dep[y]) swap(x, y);
if (x == y) return ret;
return min(ret, query_min(1, 1, n, dfn[x] + 1, dfn[y]));
}
}seg;
int main()
{
scanf("%d", &n);
for(register int i = 1, u, v, w; i < n; i++)
scanf("%d%d%d", &u, &v, &w), ++u, ++v, add(u, v, w, i), add(v, u, w, i);
dfs1(1), top[1] = 1, dfs2(1);
for(register int i = 1; i <= n; i++) seg.update_node(1, 1, n, dfn[i], edg[i]);
scanf("%d", &m);
char op[5];
for(int u, v; m; --m)
{
scanf("%s%d%d", op, &u, &v), ++u, ++v;
if (op[0] == 'C') seg.update_node(1, 1, n, dfn[ver[u - 1]], v - 1);
else if (op[0] == 'N') seg.tree_rev(u, v);
else if (op[0] == 'S') printf("%d
", seg.tree_sum(u, v));
else if (op[1] == 'A') printf("%d
", seg.tree_max(u, v));
else printf("%d
", seg.tree_min(u, v));
}
}