【学习笔记】树链剖分
NCC79601
2019-03-13 23:26:15
树链剖分，就是指**把树给剖成链，然后用数据结构进行树上的区间操作。**
比如在这份笔记中，使用树链剖分+线段树维护（[P3384](https://www.luogu.org/problemnew/show/P3384)）。
定义：一个节点$u$所有儿子中**拥有子节点最多的儿子**$v$**就是重儿子**，由$u$到$v$这条链就是重链。找到所有的重链后，就把树按照重儿子在前，轻儿子按照 dfn 的顺序投影到数据结构上的话，那么这棵树就变得类似一个区间了，维护起来也方便很多。
# 树链剖分
树链剖分要用到两次 dfs 。
### 第一次
第一次 dfs 需要记录父亲、深度、子树大小等信息，并且**按照儿子的子树大小顺序找到重儿子**。
**注意！** 在更新重儿子的时候，千万要写$size[v] > size[son[u]]$，否则找到的根本就**不是重儿子**，整份代码也就是个假的树链剖分，当时就是因为这个地方写飘了，导致 TLE 了三个点。
```cpp
inline void dfs1(int u, int fa) {
f[u] = fa, depth[u] = depth[fa] + 1;
size[u] = 1;
for(register int i = last[u]; i; i = edge[i].next) {
int v = edge[i].to;
if(v == fa)
continue;
dfs1(v, u);
size[u] += size[v];
if(size[v] > size[son[u]]) //attention!
son[u] = v;
}
return;
}
```
### 第二次
第二次 dfs 则就是拆树过程。先记录当前节点所在链的头节点$top[u]$（方便 LCA ），并且记录 dfn 序。注意：这里的 dfn 序则就是**当前节点在新树中对应的新编号**，线段树也是对这东西进行维护。但是为了方便访问，也要记录下 dfn 所对应的原数字编号$rev[cnt]$。此后，优先将当前链向下延展，然后对于所有轻儿子进行 dfs 。
```cpp
inline void dfs2(int u, int t) {
top[u] = t;
dfn[u] = ++cnt;
rev[cnt] = u;
if(!son[u])
return;
dfs2(son[u], t);
for(register int i = last[u]; i; i = edge[i].next) {
int v = edge[i].to;
if(v == f[u] || v == son[u])
continue;
dfs2(v, v);
}
return;
}
```
# 数据结构维护
线段树维护不必多说，不过建树的时候注意当$l=r$的时候，要用原数值，即$v(num) = array[rev[l]]$，否则就$gg$了。
```cpp
inline void build_tree(int l, int r, int num) {
tag(num) = 0;
l(num) = l, r(num) = r;
if(l == r) {
v(num) = array[rev[l]] % p;
return;
}
int mid = (l + r) >> 1;
build_tree(l, mid, num<<1);
build_tree(mid+1, r, num<<1|1);
v(num) = (v(num<<1) + v(num<<1|1)) % p;
return;
}
```
# 树上修改及查询
在原树上进行操作，等价于在$[u,v]$最短路中所有被包含的链进行操作。由于链被分成了一段一段的，想要精确找到这些链则是个难题。
这里用了 LCA ，不过不是倍增 LCA 。由于之前已经记录下来了父亲$f[u]$以及所在链的链头$top[u]$，所以根本不需要倍增，直接逮着开跑就行。
左右两侧节点的处理方式完全一致，以$x$节点的处理为例：
维护一个$\_x$表示当前$x$节点所在链的链头，当前处理的区间也就是$[dfn[\_x],dfn[x]]$。如果这个链头的深度比$\_y$大，说明这条链在$y$那条链下面，所以可以直接对当前区间进行数据结构操作，然后把$x$跳到$\_x$的父亲，再把$\_x$更新为新的$x$所对应的链头。
但这样子处理有个问题，那就是当$\_x$与$\_y$相同后，$x$与$y$不见得相同。因此在$while$循环外**还要再进行一次维护**，直接对$dfn[x]$与$dfn[y]$之间的区间进行操作即可。
这个样子就完成了树上操作，查询区间和以及修改区间都可以用这个方法实现。
```cpp
inline long long summary(int &x, int &y) {
long long sum = 0;
int _x = top[x], _y = top[y];
while(_x != _y) {
if(depth[_x] >= depth[_y]) {
sum = (sum + query(dfn[_x], dfn[x], 1)) % p;
x = f[_x], _x = top[x];
}
else {
sum = (sum + query(dfn[_y], dfn[y], 1)) % p;
y = f[_y], _y = top[y];
}
}
if(dfn[x] <= dfn[y])
sum = (sum + query(dfn[x], dfn[y], 1)) % p;
else
sum = (sum + query(dfn[y], dfn[x], 1)) % p;
return sum;
}
inline void update(int &x, int &y, long long c) {
int _x = top[x], _y = top[y];
while(_x != _y) {
if(depth[_x] >= depth[_y]) {
edit_tree(dfn[_x], dfn[x], 1, c);
x = f[_x], _x = top[x];
}
else {
edit_tree(dfn[_y], dfn[y], 1, c);
y = f[_y], _y = top[y];
}
}
if(dfn[x] <= dfn[y])
edit_tree(dfn[x], dfn[y], 1, c);
else
edit_tree(dfn[y], dfn[x], 1, c);
return;
}
```
# 主程序
主程序里头先$dfs1$，再从$root$进行$dfs2$，最后建树即可。
```cpp
int main() {
dfs1(r, 0);
dfs2(r, r);
build_tree(1, n, 1);
}
```
---
完整代码：
```cpp
#include<bits/stdc++.h>
#define l(x) segtree[x].l
#define r(x) segtree[x].r
#define v(x) segtree[x].val
#define tag(x) segtree[x].tag
using namespace std;
const int MAXN = 100010;
struct EDGE {
int to, next;
} edge[MAXN << 1];
int last[MAXN], id = 0;
struct SEGTREE {
long long l, r, val, tag;
} segtree[MAXN*4];
long long array[MAXN];
int f[MAXN], depth[MAXN], son[MAXN], size[MAXN];
int top[MAXN], rev[MAXN], dfn[MAXN], cnt = 0;
int n, m, p, r, a, b, opt;
long long k;
//树链剖分过程
inline void build_edge(int u, int v) {
edge[++id].to = v;
edge[id].next = last[u];
last[u] = id;
return;
}
inline void dfs1(int u, int fa) {
f[u] = fa, depth[u] = depth[fa] + 1;
size[u] = 1;
for(register int i = last[u]; i; i = edge[i].next) {
int v = edge[i].to;
if(v == fa)
continue;
dfs1(v, u);
size[u] += size[v];
if(size[v] > size[son[u]]) //attention!
son[u] = v;
}
return;
}
inline void dfs2(int u, int t) {
top[u] = t;
dfn[u] = ++cnt;
rev[cnt] = u;
if(!son[u])
return;
dfs2(son[u], t);
for(register int i = last[u]; i; i = edge[i].next) {
int v = edge[i].to;
if(v == f[u] || v == son[u])
continue;
dfs2(v, v);
}
return;
}
//线段树维护
inline void build_tree(int l, int r, int num) {
tag(num) = 0;
l(num) = l, r(num) = r;
if(l == r) {
v(num) = array[rev[l]] % p;
return;
}
int mid = (l + r) >> 1;
build_tree(l, mid, num<<1);
build_tree(mid+1, r, num<<1|1);
v(num) = (v(num<<1) + v(num<<1|1)) % p;
return;
}
inline void pushdown(int num) {
if(!tag(num))
return;
v(num<<1) = (v(num<<1) + tag(num) * (r(num<<1) - l(num<<1) + 1)) % p;
v(num<<1|1) = (v(num<<1|1) + tag(num) * (r(num<<1|1) - l(num<<1|1) + 1)) % p;
tag(num<<1) = (tag(num<<1) + tag(num)) % p;
tag(num<<1|1) = (tag(num<<1|1) + tag(num)) % p;
tag(num) = 0;
return;
}
inline void edit_tree(int l, int r, int num, long long c) {
if(l <= l(num) && r(num) <= r) {
v(num) = (v(num) + c * (r(num) - l(num) + 1)) % p;
tag(num) = (tag(num) + c) % p;
return;
}
pushdown(num);
int mid = (l(num) + r(num)) >> 1;
if(l <= mid)
edit_tree(l, r, num<<1, c);
if(r > mid)
edit_tree(l, r, num<<1|1, c);
v(num) = (v(num<<1) + v(num<<1|1)) % p;
return;
}
inline long long query(int l, int r, int num) {
if(l <= l(num) && r(num) <= r)
return v(num);
pushdown(num);
int mid = (l(num) + r(num)) >> 1;
long long sum = 0;
if(l <= mid)
sum = (sum + query(l, r, num<<1)) % p;
if(r > mid)
sum = (sum + query(l, r, num<<1|1)) % p;
return sum;
}
inline long long summary(int &x, int &y) {
long long sum = 0;
int _x = top[x], _y = top[y];
while(_x != _y) {
if(depth[_x] >= depth[_y]) {
sum = (sum + query(dfn[_x], dfn[x], 1)) % p;
x = f[_x], _x = top[x];
}
else {
sum = (sum + query(dfn[_y], dfn[y], 1)) % p;
y = f[_y], _y = top[y];
}
}
if(dfn[x] <= dfn[y])
sum = (sum + query(dfn[x], dfn[y], 1)) % p;
else
sum = (sum + query(dfn[y], dfn[x], 1)) % p;
return sum;
}
inline void update(int &x, int &y, long long c) {
int _x = top[x], _y = top[y];
while(_x != _y) {
if(depth[_x] >= depth[_y]) {
edit_tree(dfn[_x], dfn[x], 1, c);
x = f[_x], _x = top[x];
}
else {
edit_tree(dfn[_y], dfn[y], 1, c);
y = f[_y], _y = top[y];
}
}
if(dfn[x] <= dfn[y])
edit_tree(dfn[x], dfn[y], 1, c);
else
edit_tree(dfn[y], dfn[x], 1, c);
return;
}
int main() {
scanf("%d%d%d%d", &n, &m, &r, &p);
for(register int i = 1; i <= n; i++) {
scanf("%lli", &array[i]);
array[i] %= p;
}
for(register int i = 1; i < n; i++) {
scanf("%d%d", &a, &b);
build_edge(a, b);
build_edge(b, a);
}
dfs1(r, 0);
dfs2(r, r);
build_tree(1, n, 1);
for(register int i = 1; i <= m; i++) {
scanf("%d", &opt);
switch(opt) {
case 1: {
scanf("%d%d%lli", &a, &b, &k);
update(a, b, k);
break;
}
case 2: {
scanf("%d%d", &a, &b);
printf("%lli\n", summary(a, b));
break;
}
case 3: {
scanf("%d%lli", &a, &k);
edit_tree(dfn[a], dfn[a]+size[a]-1, 1, k);
break;
}
case 4: {
scanf("%d", &a);
printf("%lli\n", query(dfn[a], dfn[a]+size[a]-1, 1));
break;
}
}
}
return 0;
}
```
---
如何用树链剖分+线段树维护**树上路径颜色段数量**呢？这里记录下一个骚气的做法，线段树还可以这样用！
## 一道比较好的树剖题 [P2146](https://www.luogu.org/problemnew/show/P2146)
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
int fa[MAXN], depth[MAXN], dfn[MAXN], rev[MAXN];
int top[MAXN], size[MAXN], son[MAXN], cnt = 0;
int n, q;
struct SEGTREE {
int l, r, len;
long long tag, v;
} tree[MAXN << 2];
struct EDGE {
int to, next;
} edge[MAXN << 1];
int id = 0, last[MAXN];
inline int read() {
int res = 0, uz = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-')
uz = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
res = (res << 3) + (res << 1) + (ch ^ '0');
ch = getchar();
}
return res * uz;
}
inline void build_edge(int u, int v) {
edge[++id].to = v;
edge[id].next = last[u];
last[u] = id;
return;
}
inline void dfs1(int u, int father) {
fa[u] = father, depth[u] = depth[father] + 1;
size[u] = 1;
for(register int i = last[u]; i; i = edge[i].next) {
int v = edge[i].to;
if(v == father)
continue;
dfs1(v, u);
size[u] += size[v];
if(size[v] > size[son[u]])
son[u] = v;
}
return;
}
inline void dfs2(int u, int t) {
top[u] = t;
dfn[u] = ++cnt;
rev[cnt] = u;
if(!son[u])
return;
dfs2(son[u], t);
for(register int i = last[u]; i; i = edge[i].next) {
int v = edge[i].to;
if(v == fa[u] || v == son[u])
continue;
dfs2(v, v);
}
return;
}
inline void pushdown(int x) {
if(!~tree[x].tag)
return;
tree[x<<1].v = tree[x].tag * tree[x<<1].len;
tree[x<<1|1].v = tree[x].tag * tree[x<<1|1].len;
tree[x<<1].tag = tree[x<<1|1].tag = tree[x].tag;
tree[x].tag = -1;
return;
}
inline void build_tree(int x, int l, int r) {
tree[x].len = r - l + 1;
tree[x].tag = -1, tree[x].v = 0;
tree[x].l = l, tree[x].r = r;
if(l == r)
return;
int mid = (l + r) >> 1;
build_tree(x<<1, l, mid);
build_tree(x<<1|1, mid+1, r);
return;
}
inline long long query(int l, int r, int x) {
int ll = tree[x].l, rr = tree[x].r;
if(l <= ll && rr <= r)
return tree[x].v;
pushdown(x);
int mid = (ll + rr) >> 1;
long long res = 0;
if(l <= mid)
res += query(l, r, x<<1);
if(r > mid)
res += query(l, r, x<<1|1);
return res;
}
inline void edit_tree(int l, int r, int x, int v) {
int ll = tree[x].l, rr = tree[x].r;
if(l <= ll && rr <= r) {
tree[x].v = v * tree[x].len;
tree[x].tag = v;
return;
}
pushdown(x);
int mid = (ll + rr) >> 1;
if(l <= mid)
edit_tree(l, r, x<<1, v);
if(r > mid)
edit_tree(l, r, x<<1|1, v);
tree[x].v = tree[x<<1].v + tree[x<<1|1].v;
return;
}
inline void update(int u, int v, int val) {
while(top[u] != top[v]) {
if(depth[top[u]] < depth[top[v]])
swap(u, v);
edit_tree(dfn[top[u]], dfn[u], 1, val);
u = fa[top[u]];
}
if(dfn[u] > dfn[v])
swap(u, v);
edit_tree(dfn[u], dfn[v], 1, val);
return;
}
int main() {
n = read();
for(register int i = 2; i <= n; i++) {
int depend = read() + 1;
build_edge(depend, i);
}
dfs1(1, 1);
dfs2(1, 1);
build_tree(1, 1, cnt);
char s[20];
q = read();
while(q--) {
scanf("%s", s);
int app = read() + 1;
int pre = tree[1].v;
if(s[0] == 'i') {
update(1, app, 1);
printf("%lli\n", abs(tree[1].v - pre));
}
if(s[0] == 'u') {
edit_tree(dfn[app], dfn[app] + size[app] - 1, 1, 0);
printf("%lli\n", abs(tree[1].v - pre));
}
}
return 0;
}
```
---
还有类似对边权处理、对区间取相反数的问题，都可以用树链剖分解决，可以把边权全部投影到**后向点**（边两端深度最大的点）上，处理一段路径的时候注意**不能把 LCA 给处理了，否则直接$gg$**。
另外，取相反数的$lazytag$在下放、修改时有**注意事项**，相当于是$tree[x].tag\otimes1\,($取**异或**$)$,具体直接看代码。
## 例题 [P1505](https://www.luogu.org/problemnew/show/P1505)
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000010;
const int INF = 1 << 30;
struct EDGE {
int to, next, val;
} edge[MAXN << 1];
int last[MAXN], id = 0;
struct SEGTREE {
int l, r, tag;
int v, max, min;
} tree[MAXN << 2];
inline int read() {
int res = 0, uz = 1;
char ch = getchar();
while(!isdigit(ch)) {
if(ch == '-')
uz = -1;
ch = getchar();
}
while(isdigit(ch)) {
res = (res << 3) + (res << 1) + (ch ^ '0');
ch = getchar();
}
return res * uz;
}
inline void build_edge(int u, int v, int val) {
edge[++id].to = v;
edge[id].val = val;
edge[id].next = last[u];
last[u] = id;
return;
}
int w[MAXN];
int size[MAXN], son[MAXN], depth[MAXN], fa[MAXN];
int top[MAXN], dfn[MAXN], rev[MAXN], cnt = 0;
int n;
inline void dfs1(int u, int father) {
fa[u] = father, depth[u] = depth[father] + 1;
size[u] = 1;
for(register int i = last[u]; i; i = edge[i].next) {
int v = edge[i].to;
if(v == father)
continue;
w[v] = edge[i].val;
dfs1(v, u);
size[u] += size[v];
if(size[v] > size[son[u]])
son[u] = v;
}
return;
}
inline void dfs2(int u, int t) {
dfn[u] = ++cnt, rev[cnt] = u;
top[u] = t;
if(!son[u])
return;
dfs2(son[u], t);
for(register int i = last[u]; i; i = edge[i].next) {
int v = edge[i].to;
if(v == fa[u] || v == son[u])
continue;
dfs2(v, v);
}
return;
}
inline void pushdown(int x) {
if(!tree[x].tag)
return;
//left
tree[x<<1].tag += tree[x].tag;
tree[x<<1].tag %= 2; //^=1
tree[x<<1].v *= -1;
swap(tree[x<<1].max, tree[x<<1].min);
tree[x<<1].max *= -1, tree[x<<1].min *= -1;
//right
tree[x<<1|1].tag += tree[x].tag;
tree[x<<1|1].tag %= 2; //^=1
tree[x<<1|1].v *= -1;
swap(tree[x<<1|1].max, tree[x<<1|1].min);
tree[x<<1|1].max *= -1, tree[x<<1|1].min *= -1;
tree[x].tag = 0;
return;
}
inline void pushup(int x) {
tree[x].v = tree[x<<1].v + tree[x<<1|1].v;
tree[x].max = max(tree[x<<1].max, tree[x<<1|1].max);
tree[x].min = min(tree[x<<1].min, tree[x<<1|1].min);
return;
}
inline void build_tree(int x, int l, int r) {
//printf("build %d->[%d,%d]\n", x, l, r);
tree[x].l = l, tree[x].r = r;
tree[x].tag = 0;
if(l == r) {
tree[x].v = tree[x].max = tree[x].min = w[rev[l]];
return;
}
int mid = (l + r) >> 1;
build_tree(x<<1, l, mid);
build_tree(x<<1|1, mid+1, r);
pushup(x);
return;
}
inline void edit_tree(int x, int p, int c) {
//printf("edit_tree p:%d now:%d->[%d,%d]->%d\n", p, x, tree[x].l, tree[x].r, c);
if(tree[x].l == tree[x].r) {
tree[x].v = tree[x].max = tree[x].min = c;
return;
}
pushdown(x);
int mid = (tree[x].l + tree[x].r) >> 1;
if(p <= mid)
edit_tree(x<<1, p, c);
else
edit_tree(x<<1|1, p, c);
pushup(x);
return;
}
inline void reverse_tree(int x, int l, int r) {
int ll = tree[x].l, rr = tree[x].r;
if(l <= ll && rr <= r) {
tree[x].tag ^= 1;
tree[x].v *= -1;
swap(tree[x].max, tree[x].min);
tree[x].max *= -1, tree[x].min *= -1;
return;
}
pushdown(x);
int mid = (ll + rr) >> 1;
if(l <= mid)
reverse_tree(x<<1, l, r);
if(r > mid)
reverse_tree(x<<1|1, l, r);
pushup(x);
return;
}
inline int query_sum(int x, int l, int r) {
//printf("querysum %d->[%d,%d]\n", x, l, r);
int ll = tree[x].l, rr = tree[x].r;
if(l <= ll && rr <= r)
return tree[x].v;
pushdown(x);
int mid = (ll + rr) >> 1;
int res = 0;
if(l <= mid)
res += query_sum(x<<1, l, r);
if(r > mid)
res += query_sum(x<<1|1, l, r);
return res;
}
inline int query_max(int x, int l, int r) {
int ll = tree[x].l, rr = tree[x].r;
if(l <= ll && rr <= r)
return tree[x].max;
pushdown(x);
int res = -INF;
int mid = (ll + rr) >> 1;
if(l <= mid)
res = max(res, query_max(x<<1, l, r));
if(r > mid)
res = max(res, query_max(x<<1|1, l, r));
return res;
}
inline int query_min(int x, int l, int r) {
int ll = tree[x].l, rr = tree[x].r;
if(l <= ll && rr <= r)
return tree[x].min;
pushdown(x);
int res = INF;
int mid = (ll + rr) >> 1;
if(l <= mid)
res = min(res, query_min(x<<1, l, r));
if(r > mid)
res = min(res, query_min(x<<1|1, l, r));
return res;
}
inline int Sum(int u, int v) {
int res = 0;
while(top[u] != top[v]) {
if(depth[top[u]] < depth[top[v]])
swap(u, v);
res += query_sum(1, dfn[top[u]], dfn[u]);
u = fa[top[u]];
}
if(dfn[u] > dfn[v])
swap(u, v);
res += query_sum(1, dfn[u]+1, dfn[v]);
return res;
}
inline void Reverse(int u, int v) {
while(top[u] != top[v]) {
if(depth[top[u]] < depth[top[v]])
swap(u, v);
reverse_tree(1, dfn[top[u]], dfn[u]);
u = fa[top[u]];
}
if(dfn[u] > dfn[v])
swap(u, v);
reverse_tree(1, dfn[u]+1, dfn[v]);
return;
}
inline int Max(int u, int v) {
int res = -INF;
while(top[u] != top[v]) {
if(depth[top[u]] < depth[top[v]])
swap(u, v);
res = max(res, query_max(1, dfn[top[u]], dfn[u]));
u = fa[top[u]];
}
if(dfn[u] > dfn[v])
swap(u, v);
res = max(res, query_max(1, dfn[u]+1, dfn[v]));
return res;
}
inline int Min(int u, int v) {
int res = INF;
while(top[u] != top[v]) {
if(depth[top[u]] < depth[top[v]])
swap(u, v);
res = min(res, query_min(1, dfn[top[u]], dfn[u]));
u = fa[top[u]];
}
if(dfn[u] > dfn[v])
swap(u, v);
res = min(res, query_min(1, dfn[u]+1, dfn[v]));
return res;
}
int main() {
n = read();
for(register int i = 1; i < n; i++) {
int u, v, w;
u = read() + 1, v = read() + 1, w = read();
build_edge(u, v, w);
build_edge(v, u, w);
}
dfs1(1, 1);
dfs2(1, 1);
build_tree(1, 1, n);
int m = read();
while(m--) {
char s[10];
int a, b;
scanf("%s", s);
a = read(); b = read();
if(s[0] == 'C')
edit_tree(1, dfn[++a], b);
else if(s[0] == 'N')
Reverse(++a, ++b);
else if(s[0] == 'S')
printf("%d\n", Sum(++a, ++b));
else if(s[1] == 'A')
printf("%d\n", Max(++a, ++b));
else
printf("%d\n", Min(++a, ++b));
}
return 0;
}
```
---
## 例题 [P4315](https://www.luogu.org/problemnew/show/P4315)
这道题的核心就是如何正确地打 **[线段树](https://ncc79601.blog.luogu.org/post-xue-xi-bi-ji-xian-duan-shu)** ，以及如何处理**单独修改边权**的问题。
**修改第$\textbf{u}$条边时，加上这句话：**
```cpp
u = depth[edge[(u<<1)-1].to] < depth[edge[u<<1].to] ? edge[u<<1].to : edge[(u<<1)-1].to;
```
意思是说，判断当前这条边的边权投影到的是哪个点。由于输入的$u$是表示第$u$条边，由于我们存的是无向边，所以$2u-1$、$2u$编号的边都是“第$u$条边”，由于投影时是将边权保存到边的后向点，所以只需要找到**深度最大的那个点**即可。
---
完整代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
const int INF = 1 << 30;
struct EDGE {
int to, next;
int val;
} edge[MAXN];
int last[MAXN], id = 0;
struct SEGTREE {
int l, r;
int tag, c, max;
} tree[MAXN << 2];
inline void build_edge(int u, int v, int val) {
edge[++id].to = v;
edge[id].val = val;
edge[id].next = last[u];
last[u] = id;
return;
}
int n, w[MAXN];
int fa[MAXN], depth[MAXN], size[MAXN], son[MAXN];
int top[MAXN], dfn[MAXN], rev[MAXN], cnt = 0;
inline void dfs1(int u, int father) {
fa[u] = father, depth[u] = depth[father] + 1;
size[u] = 1;
for(register int i = last[u]; i; i = edge[i].next) {
int v = edge[i].to;
if(v == father)
continue;
w[v] = edge[i].val;
dfs1(v, u);
size[u] += size[v];
if(size[v] > size[son[u]])
son[u] = v;
}
return;
}
inline void dfs2(int u, int t) {
top[u] = t;
dfn[u] = ++cnt, rev[cnt] = u;
if(!son[u])
return;
dfs2(son[u], t);
for(register int i = last[u]; i; i = edge[i].next) {
int v = edge[i].to;
if(v == fa[u] || v == son[u])
continue;
dfs2(v, v);
}
return;
}
inline void pushdown(int x) {
if(~tree[x].c) {
tree[x<<1].max = tree[x<<1|1].max = tree[x].c;
tree[x<<1].c = tree[x<<1|1].c = tree[x].c;
tree[x<<1].tag = tree[x<<1|1].tag = 0;
tree[x].c = -1;
}
if(tree[x].tag) {
tree[x<<1].max += tree[x].tag;
tree[x<<1|1].max += tree[x].tag;
tree[x<<1].tag += tree[x].tag;
tree[x<<1|1].tag += tree[x].tag;
tree[x].tag = 0;
}
return;
}
inline void pushup(int x) {
tree[x].max = max(tree[x<<1].max, tree[x<<1|1].max);
return;
}
inline void build_tree(int x, int l, int r) {
tree[x].l = l, tree[x].r = r;
tree[x].tag = 0, tree[x].c = -1;
if(l == r) {
tree[x].max = w[rev[l]];
return;
}
int mid = (l + r) >> 1;
build_tree(x<<1, l, mid);
build_tree(x<<1|1, mid + 1, r);
pushup(x);
return;
}
inline void cover(int x, int l, int r, int c) {
int ll = tree[x].l, rr = tree[x].r;
if(l <= ll && rr <= r) {
tree[x].max = tree[x].c = c;
tree[x].tag = 0;
return;
}
pushdown(x);
int mid = (ll + rr) >> 1;
if(l <= mid)
cover(x<<1, l, r, c);
if(r > mid)
cover(x<<1|1, l, r, c);
pushup(x);
return;
}
inline void add(int x, int l, int r, int c) {
int ll = tree[x].l, rr = tree[x].r;
if(l <= ll && rr <= r) {
tree[x].max += c;
tree[x].tag += c;
return;
}
pushdown(x);
int mid = (ll + rr) >> 1;
if(l <= mid)
add(x<<1, l, r, c);
if(r > mid)
add(x<<1|1, l, r, c);
pushup(x);
return;
}
inline int query(int x, int l, int r) {
int res = -INF;
int ll = tree[x].l, rr = tree[x].r;
if(l <= ll && rr <= r)
return tree[x].max;
pushdown(x);
int mid = (ll + rr) >> 1;
if(l <= mid)
res = max(res, query(x<<1, l, r));
if(r > mid)
res = max(res, query(x<<1|1, l, r));
return res;
}
inline void Cover(int u, int v, int c) {
while(top[u] != top[v]) {
if(depth[top[u]] < depth[top[v]])
swap(u, v);
cover(1, dfn[top[u]], dfn[u], c);
u = fa[top[u]];
}
if(dfn[u] > dfn[v])
swap(u, v);
cover(1, dfn[u] + 1, dfn[v], c);
return;
}
inline void Add(int u, int v, int c) {
while(top[u] != top[v]) {
if(depth[top[u]] < depth[top[v]])
swap(u, v);
add(1, dfn[top[u]], dfn[u], c);
u = fa[top[u]];
}
if(dfn[u] > dfn[v])
swap(u, v);
add(1, dfn[u] + 1, dfn[v], c);
return;
}
inline int Max(int u, int v) {
int res = -INF;
while(top[u] != top[v]) {
if(depth[top[u]] < depth[top[v]])
swap(u, v);
res = max(res, query(1, dfn[top[u]], dfn[u]));
u = fa[top[u]];
}
if(dfn[u] > dfn[v])
swap(u, v);
res = max(res, query(1, dfn[u] + 1, dfn[v]));
return res;
}
int main() {
scanf("%d", &n);
for(register int i = 1; i < n; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
build_edge(u, v, w);
build_edge(v, u, w);
}
dfs1(1, 1);
dfs2(1, 1);
build_tree(1, 1, n);
char s[10];
scanf("%s", s);
while(s[0] != 'S') {
switch(s[1]) {
case 'a': {
int u, v;
scanf("%d%d", &u, &v);
printf("%d\n", Max(u, v));
break;
}
case 'o': {
int u, v, c;
scanf("%d%d%d", &u, &v, &c);
Cover(u, v, c);
break;
}
case 'd': {
int u, v, c;
scanf("%d%d%d", &u, &v, &c);
Add(u, v, c);
break;
}
case 'h': {
int u, c;
scanf("%d%d", &u, &c);
u = depth[edge[(u<<1)-1].to] < depth[edge[u<<1].to] ? edge[u<<1].to : edge[(u<<1)-1].to;
cover(1, dfn[u], dfn[u], c);
break;
}
}
scanf("%s", s);
}
return 0;
}
```