前言

题目链接：洛谷 P4114 Qtree1

前置知识：树链剖分

---

题意

给定一棵树，有修改边权和查询两点之间边权最大值两种操作，对于每个查询输出结果。

解析

已经在前置博客里提到，树链剖分 可以将树上的任意一条路径划分成不超过 \(O(\log n)\) 条连续的链，保证划分出的每条链上的节点 DFS 序 连续。这大大方便了我们维护点权，但该如何维护边权呢？

这里就要介绍一种重要的思想——化边权为点权。

从 \(1\) 号点开始，遍历一遍整棵树，对于每条边，把边权赋在后遍历到的那个点，也就是 \(dep\) 更大的点上。这样可以保证，在跳祖先的过程中，必然能够不重不漏地计算到每个边权。若把边权赋在 \(dep\) 更大的点上则不然。最后就是简单的 树剖+线段树 维护最大值的过程。

查询操作不用多说，就是树剖的常规操作，不断跳祖先查询最大值即可。

修改操作就比较复杂了，要找到第 \(i\) 条边上 \(dep\) 较大的点（因为边权存在这个点上），然后使用线段树单点修改。

这里要注意，使用 链式前向星 存图会比 vector 邻接表方便更多，因为我们要找到输入的第 \(i\) 条边。

代码

// Problem: P4114 Qtree1
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4114
// Memory Limit: 500 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 100005;
int n, u, v, w, cnt, tot, a, b;
int head[N], top[N], dep[N], dfn[N], heavy[N], son[N], val[N], f[N];
string s;

struct edge
{
    int from, to, val, nxt;
}e[N << 1];

inline void add_edge(int u, int v, int w)
{
    e[++tot] = {u, v, w, head[u]}, head[u] = tot;
}

inline void dfs1(int u, int fa)
{
    dep[u] = dep[fa] + 1, f[u] = fa, son[u] = 1;
    for(int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == fa) continue;
        dfs1(v, u);
        son[u] += son[v];
        if(son[heavy[u]] <= son[v]) heavy[u] = v;
    }
    return;
}

inline void dfs2(int u, int tp)
{
    top[u] = tp, dfn[u] = ++cnt;
    if(!heavy[u]) return;
    dfs2(heavy[u], tp);
    for(int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == f[u] || v == heavy[u]) continue;
        dfs2(v, v);
    }
    return;
}

struct node
{
    int l, r, maxi;
}tree[N << 2];

inline void push_up(int x)
{
    tree[x].maxi = max(tree[x << 1].maxi, tree[x << 1 | 1].maxi);
}

inline void build(int l, int r, int x)
{
    tree[x] = {l, r, 0};
    if(l == r) return (void) (tree[x].maxi = val[l]);
    int mid = l + r >> 1;
    build(l, mid, x << 1);
    build(mid + 1, r, x << 1 | 1);
    push_up(x);
    return;
}

inline void update(int pos, int k, int x)
{
    if(tree[x].l == tree[x].r && tree[x].r == pos)
        return (void) (tree[x].maxi = k);
    int mid = tree[x].l + tree[x].r >> 1;
    if(pos <= mid) update(pos, k, x << 1);
    if(pos > mid) update(pos, k, x << 1 | 1);
    push_up(x);
    return;
}

inline int query(int l, int r, int x)
{
    if(l <= tree[x].l && tree[x].r <= r) return tree[x].maxi;
    int mid = tree[x].l + tree[x].r >> 1, ans = 0;
    if(l <= mid) ans = max(ans, query(l, r, x << 1));
    if(r > mid) ans = max(ans, query(l, r, x << 1 | 1));
    return ans;
}

inline int ask(int x, int y)
{
    int ans = 0;
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        ans = max(ans, query(dfn[top[x]], dfn[x], 1));
        x = f[top[x]];
    }
    if(dfn[x] > dfn[y]) swap(x, y);
    return max(ans, query(dfn[x] + 1, dfn[y], 1));
}

signed main()
{
    ios :: sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        cin >> u >> v >> w;
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    for(int i = 1; i <= tot; i += 2)
    {
        int u = e[i].from, v = e[i].to;
        if(dep[u] < dep[v]) swap(u, v);
        val[dfn[u]] = e[i].val;
    }
    build(1, n, 1);
    while(cin >> s)
    {
        if(s == "DONE") break;
        cin >> a >> b;
        if(s == "CHANGE")
        {
            a = a * 2 - 1;
            int u = e[a].from, v = e[a].to;
            if(dep[u] < dep[v]) swap(u, v);
            update(dfn[u], b, 1);
        }
        else cout << (a == b ? 0 : ask(a, b)) << '\n';
    }
    return 0;
}