esquigybcu @ 2022-01-19 16:25:39
```cpp
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <algorithm>
using std::max;
const int N = 2e5 + 5;
inline int fread()
{
int n = 0;
char c = getchar();
while (c < '0' || c > '9') c = getchar();
while ('0' <= c && c <= '9') n = (n << 3) + (n << 1) + c - '0', c = getchar();
return n;
}
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug printf
#endif
struct node
{
int l, r;
int val;
};
struct segtree
{
node a[N << 2];
# define u a[i]
# define lc a[i << 1]
# define rc a[i << 1 | 1]
# define mid (u.l + u.r) >> 1
# define len(v) (v.r - v.l)
inline void pushup(int i)
{
u.val = max(lc.val, rc.val);
}
inline void build(int i, int l, int r)
{
u.l = l, u.r = r;
if (len(u) == 1)
{
u.val = 0;
return;
}
build(i << 1, l, mid);
build(i << 1 | 1, mid, r);
pushup(i);
}
inline void modify(int i, int x, int k)
{
if (x < u.l || x >= u.r)
return;
if (len(u) == 1)
{
u.val = k;
return;
}
if (x < mid) modify(i << 1, x, k);
else modify(i << 1 | 1, x, k);
pushup(i);
}
inline int query(int i, int l, int r)
{
if (r <= u.l || l >= u.r)
return INT_MIN;
if (l <= u.l && r >= u.r)
return u.val;
return max(query(i << 1, l, r), query(i << 1 | 1, l, r));
}
# undef u
# undef lc
# undef rc
# undef mid
# undef len
}
QwQ;
struct edge
{
int u, v, w, next;
}
e[N << 1]; int cnt, head[N];
inline void add_edge(int u, int v, int w)
{
e[cnt].u = u, e[cnt].v = v, e[cnt].w = w, e[cnt].next = head[u];
head[u] = cnt++;
}
int depth[N], father[N], size[N], hson[N];
int dfn[N], top[N], dfscnt;
inline void dfs1(int u, int f)
{
depth[u] = depth[f] + 1;
father[u] = f;
size[u] = 1;
int qwq = 0;
for (int i = head[u]; ~i; i = e[i].next)
if (e[i].v != f)
{
int v = e[i].v;
dfs1(v, u); size[u] += size[v];
if (size[v] > qwq) qwq = size[v], hson[u] = v;
}
debug("hson[%d] = %d\n", u, hson[u]);
}
inline void dfs2(int u, int f)
{
dfn[u] = dfscnt++;
top[u] = f;
if (size[u] == 1) return;
dfs2(hson[u], hson[u]);
for (int i = head[u]; ~i; i = e[i].next)
if (e[i].v != father[u] && e[i].v != hson[u])
dfs2(e[i].v, e[i].v);
}
inline void edge_modify(int u, int k)
{
QwQ.modify(1, dfn[u], k);
}
inline int chain_query(int u, int v)
{
int ans = INT_MIN;
while (top[u] != top[v])
{
if (depth[top[u]] < depth[top[v]])
std::swap(u, v);
ans = max(ans, QwQ.query(1, dfn[top[u]], dfn[u] + 1));
u = father[top[u]];
}
if (depth[u] < depth[v])
std::swap(u, v);
ans = max(ans, QwQ.query(1, dfn[v] + 1, dfn[u] + 1));
return ans;
}
int cat[N], lhq[N], chtholly;
// cat[i]: 第 i 条边对应着 e[几]
// lhq[i]: 第 i 条边深度比较深的那个
int main()
{
memset(head, -1, sizeof head);
int n;
n = fread();
for (int i = 0; i < n - 1; i++)
{
int u, v, w;
u = fread(), v = fread(), w = fread();
cat[++chtholly] = cnt;
add_edge(u, v, w), add_edge(v, u, w);
}
dfs1(1, 0);
dfs2(1, 1);
QwQ.build(1, 0, n);
for (int i = 1; i < n; i++)
{
int qwq = cat[i], u = e[qwq].u, v = e[qwq].v;
debug("qwq = %d, u = %d, v = %d, depth[u] = %d, depth[v] = %d\n", qwq, u, v, depth[u], depth[v]);
if (depth[u] < depth[v])
std::swap(u, v);
lhq[i] = u; edge_modify(u, e[qwq].w);
debug("cat[%d] = %d, lhq[%d] = %d\n", i, cat[i], i, lhq[i]);
}
while (true)
{
char op[114]; scanf(" %s", op);
if (op[0] == 'C')
{
int x, t;
x = fread(), t = fread();
edge_modify(lhq[x], t);
}
if (op[0] == 'Q')
{
int u, v;
u = fread(), v = fread();
if (u == v) printf("0\n");
else printf("%d\n", chain_query(u, v));
}
if (op[0] == 'D') break;
}
return 0;
}
```