题面

题目链接

大秦 为你打开 题目传送门

备用题面

给定了一个树（一个无环无向连通图）包含 $N$ 个节点，以及编号为 $1$ 到 $N−1$ 的边。

你需要执行以下两种指令：

  • CHANGE i t ：将第 $i$ 条边的费用改为 $t$ 。
  • QUERY a b ：询问从节点 $a$ 到节点 $b$ 的路径上的最大边费用。

思路

基础构建

首先我们要有一个共识，就是遇到这种树上边权操作的题目一定要往边权转化为点权的思路上想一想。为什么这么说呢，如果是点权的话，我们可以遍历啊等等各种方式去维护，但是如果是边权就会变得麻烦，因为两个点之间就是一条边，我们可以认为图是若干条点与点的关系构成的，那么维护点肯定比维护边要方便，因为我们的数据记在点上就可以通过给出的若干关系来得出答案。

那么这种题我们要如何把点权转化为边权呢？这就有一个常用技巧。对于树上一条边来说，我们习惯把边的信息记载儿子方向的点上面，因为对于树来说，一个父亲可以有多个儿子，但是一个儿子只能有一个父亲，这样的映射关系就告诉我们存在儿子方面一定不会有冲突。

那么如果我们把一个问题的边权转化成了点权，那么这道题就从一个修改边权的问题变成了修改点权的问题。修改点圈，并且多组操作，还要查询，不难想到了线段树。而树上的线段树我们就需要树链剖分来解决树化为区间的操作。

友情链接：

【算法介绍】树链剖分 | 祝馀宫

进步构想

大致的思考方向我们有了，接下来就要开始想如何解决它。那么现在单点修改肯定不用我说了，问题就是如何求路径上一段路径上边的最小值。那么由于是路径问题，所以直接用重链剖分，然后重链剖分在我们使用的过程中主要是两个部分：整条重链的跳跃以及最后一段的跳跃

先来回顾一下重链剖分的基础模板：

1
2
3
4
5
6
7
8
9
inline void Calc(int u, int v) {
    while(top[u] != top[v]) {
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        // do sth.
        u = fa[top[u]];
    }
    if(dep[u] > dep[v]) swap(u, v);
    // do sth.
}

那么对于整条链的跳跃来说，我们可以概括为下面这样的图。

整条链的迁跃图

大概就是这个意思。由于我们最后要多跳到 top 的父亲，所以说这里的查询是要包含 top 的，毕竟 top 上存储的他到他父亲的边信息。那么如果是最后两个点以及在同一条重链上的时候，就要注意了。由于两个点在同一个重链上，也就是说这时候在顶端的点就不可以取了，因为如果这时候取了他，就说明你多取了一条路径之外的边，他是 LCA 到 LCA 的父亲的这条边，你多选了他，也就是说这时候较浅的哪个不用取（绝对不是应为我懒才不画图）

有了这些思路，也就差不多可以开始写代码了（呵呵呵我是一遍过

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
// typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

struct Node {
    // some basic viariables
    ll mx;
    Node() { mx = -1e18; }
    Node operator + (const Node& b) const {
        Node ans; 
        ans.mx = max(mx, b.mx); 
        return ans;
    }
};
template<const int N>
class SegTree {
private: 
    Node node[N];
    int lc[N], rc[N], cntn;
    ll lazy[N];
public :
    // clear function
    void clear(int rt) {
        if(!rt) return ;
        lazy[rt] = 0, node[rt] = Node();
        clear(lc[rt]);
        clear(rc[rt]);
        lc[rt] = rc[rt] = 0;
    }
    inline int newNode() {
        cntn++;
        lc[cntn] = rc[cntn] = lazy[cntn] = 0;
        return cntn;
    }
    // AddOperation    now   nowl   nowr  addval
    inline void Add(int rt, int l, int r, ll val) {
        node[rt].mx = val;
    }
    // PushDownOperation    now   nowl   nowr
    inline void PushDown(int rt, int l, int r) {
        if(l == r || !lazy[rt]) return ;
        int mid = (l + r) >> 1;
        if(!lc[rt]) lc[rt] = newNode();
        Add(lc[rt], l, mid, lazy[rt]);
        if(!rc[rt]) rc[rt] = newNode();
        Add(rc[rt], mid + 1, r, lazy[rt]);
        lazy[rt] = 0;
    }
    // range Modify now   nowl   nowr   qizl   qizr   addval
    void Modify(int &rt, int l, int r, int L, int R, ll val) {
        if(!rt) rt = newNode();
        if(L <= l && r <= R) {
            Add(rt, l, r, val);
            return;
        }
        PushDown(rt, l, r);
        int mid = (l + r) >> 1;
        if(L <= mid) Modify(lc[rt], l, mid, L, R, val);
        if(R > mid) Modify(rc[rt], mid + 1, r, L, R, val);
        node[rt] = node[lc[rt]] + node[rc[rt]];
    }
    // range Query now   nowl   nowr   qizl   qizr
    Node Query(int &rt, int l, int r, int L, int R) {
        if(!rt) rt = newNode();
        if(L <= l && r <= R) return node[rt];
        PushDown(rt, l, r);
        int mid = (l + r) >> 1;
        Node res; 
        // set some basic value for res
        res.mx = -1e18;
        if(L <= mid) res = res + Query(lc[rt], l, mid, L, R);
        if(R > mid) res = res + Query(rc[rt], mid + 1, r, L, R);
        return res;
    }
};

template<int N, int M>
class Graph {
    private :
        struct Edge {
            int to, nt, wt;
            Edge() {}
            Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
        }e[M];
        int hd[N], cnte;
    public :
        inline void clear() { memset(hd, 0, sizeof(hd)), cnte = 0; }
        inline void AddEdge(int u, int v, int w = 0) {
            e[++cnte] = Edge(v, hd[u], w);
            hd[u] = cnte;
        }
        inline int head(int u) { return hd[u]; }
        inline int nt(int u) { return e[u].nt; }
        inline int to(int u) { return e[u].to; }
        inline int wt(int u) { return e[u].wt; }
};

const int MaxV = 1e5 + 10;
const int MaxE = 2e5 + 10;

int n;
struct Edge {
    int u, v, w;
}e[MaxE];
Graph< MaxV, MaxE >G;

inline void Input() {
    read(n);
    for(int i = 1; i < n; i++) {
        read(e[i].u, e[i].v, e[i].w);
        G.AddEdge(e[i].u, e[i].v);
        G.AddEdge(e[i].v, e[i].u);
    }
}

int fa[MaxV], dep[MaxV];
int sz[MaxV], son[MaxV];
int top[MaxV];
int it[MaxV], cntd;

void Dfs(int u, int F) {
    fa[u] = F, dep[u] = dep[F] + 1, sz[u] = 1;
    for(int i = G.head(u); i; i = G.nt(i)) {
        int v = G.to(i);
        if(v == F) continue;
        Dfs(v, u);
        sz[u] += sz[v];
        if(sz[son[u]] < sz[v]) son[u] = v;
    }
}

void Dfs2(int u, int tp) {
    it[u] = ++cntd;
    top[u] = tp;
    if(!son[u]) return ;
    Dfs2(son[u], tp);
    for(int i = G.head(u); i; i = G.nt(i)) {
        int v = G.to(i);
        if(v == fa[u] || v == son[u]) continue;
        Dfs2(v, v);
    }
}

SegTree< MaxV << 5 >Tree; int rt;

inline void Getsum(int u, int v) {
    ll ans = 0;
    while(top[u] != top[v]) {
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        ans = max(ans, Tree.Query(rt, 1, n, it[top[u]], it[u]).mx);
        u = fa[top[u]];
    }
    if(u != v) {
        if(dep[u] > dep[v]) swap(u, v);
        ans = max(ans, Tree.Query(rt, 1, n, it[son[u]], it[v]).mx);
    }
    printf("%lld\n", ans);
}

inline void Work() {
    Dfs(1, 1), Dfs2(1, 1);
    for(int i = 1; i < n; i++) {
        // cout << it[e[i].u] << ' ' << it[e[i].v] << endl;
        if(dep[e[i].u] < dep[e[i].v]) swap(e[i].u, e[i].v);
        Tree.Modify(rt, 1, n, it[e[i].u], it[e[i].u], e[i].w);
    }
    char s[10]; int x, y;
    while(1) {
        scanf("%s", s + 1);
        if(s[1] == 'D') break;
        read(x, y);
        if(s[1] == 'C') {
            Tree.Modify(rt, 1, n, it[e[x].u], it[e[x].u], y);
        }
        else {
            Getsum(x, y);
        }
    }
}

inline void Clear() {
    Tree.clear(rt); rt = 0;
    G.clear(); cntd = 0;
    memset(fa, 0, sizeof(fa));
    memset(dep, 0, sizeof(dep));
    memset(sz, 0, sizeof(sz));
    memset(it, 0, sizeof(it));
    memset(son, 0, sizeof(son));
    memset(top, 0, sizeof(top));
}

int main() {
    int T = read();
    while(T--) {
        Clear();
        Input();
        Work();
    }
    return 0;
}