题目链接：HDU-6547 Tree
题意
wls 有三棵树，树上每个节点都有一个值 $a_i$，现在有 2 种操作：
1. 将一条链上的所有节点的值开根号向下取整；
2. 求一条链上值的和；
链的定义是两点之间的最短路。
思路
树链剖分裸题，区间开根号可用线段树做，利用 $10^9$ 范围内的数经过少数几次开根号之后就会达到 1，标记线段树区间最大值，若为 1 则无需再往下更新。
树链剖分传送门：https://www.cnblogs.com/kangkang-/p/8486150.html
代码实现
#include <stdio.h> #include <iostream> #include <cmath> #define REP(i, a, b) for (int i = a; i <= b; i++) using namespace std; typedef long long LL; const double esp = 1e-8; const int MAXN = 110000; struct Node { int to, next; } edg[MAXN<<1]; struct segmentTree { int left, right; LL sum, maxx; } tree[MAXN<<2]; int head[MAXN], siz[MAXN], top[MAXN], hson[MAXN], dep[MAXN], fa[MAXN], id[MAXN], rnk[MAXN]; int N, M, R, A[MAXN], idx = 0, dfs_cnt = 0; inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } inline void adde(int u, int v) { edg[++idx].to = v; edg[idx].next = head[u]; head[u] = idx; } void dfs1(int u, int father, int depth) { dep[u] = depth; fa[u] = father; siz[u] = 1; for (int i = head[u]; i; i = edg[i].next) { int v = edg[i].to; if (v != fa[u]) { dfs1(v, u, depth + 1); siz[u] += siz[v]; if (hson[u] == -1 || siz[v] > siz[hson[u]]) hson[u] = v; } } } void dfs2(int u, int t) { id[u] = ++dfs_cnt; rnk[dfs_cnt] = u; top[u] = t; if (!hson[u]) return ; dfs2(hson[u], t); for (int i = head[u]; i; i = edg[i].next) { int v = edg[i].to; if (v != hson[u] && v != fa[u]) dfs2(v, v); } } void buildtree(int i, int l, int r) { tree[i].left = l; tree[i].right = r; if (l == r) tree[i].sum = tree[i].maxx = A[rnk[l]]; else { int mid = (l + r) >> 1; buildtree(i << 1, l , mid); buildtree(i << 1 | 1, mid + 1, r); tree[i].sum = tree[i<<1].sum + tree[i<<1|1].sum; tree[i].maxx = max(tree[i<<1].maxx, tree[i<<1|1].maxx); } } void update(int i, int x, int y) { if (tree[i].left > y || tree[i].right < x) return ; if (tree[i].left == tree[i].right) { tree[i].maxx = sqrt(tree[i].maxx) + esp; tree[i].sum = sqrt(tree[i].sum) + esp; return ; } if (tree[i].maxx == 1) return ; int l = i << 1, r = i << 1 | 1; update(l, x, y); update(r, x, y); tree[i].sum = tree[l].sum + tree[r].sum; } LL query(int i, int x, int y) { int l = i << 1, r = i << 1 | 1; if (x <= tree[i].left && tree[i].right <= y) return tree[i].sum; if (tree[i].left > y || tree[i].right < x) return 0; return query(l, x, y) + query(r, x, y); } void update_path(int u, int v) { int tu = top[u], tv = top[v]; while (tu != tv) { if (dep[tu] < dep[tv]) swap(u, v), swap(tu, tv); update(1, id[tu], id[u]); u = fa[tu], tu = top[u]; } if (dep[u] < dep[v]) swap(u, v); update(1, id[v], id[u]); } LL query_path(int u, int v) { LL res = 0; int tu = top[u], tv = top[v]; while (tu != tv) { if (dep[tu] < dep[tv]) swap(u, v), swap(tu, tv); res += query(1, id[tu], id[u]); u = fa[tu], tu = top[u]; } if (dep[u] < dep[v]) swap(u, v); return res + query(1, id[v], id[u]); } int main() { N = read(), M = read(), R = 1; REP(i, 1, N) A[i] = read(); REP(i, 2, N) { int u = read(), v = read(); adde(u, v); adde(v, u); } dfs1(R, 0, 1); dfs2(R, R); buildtree(1, 1, N); while (M--) { int opt = read(); switch (opt) { case 0: { int x = read(), y = read(); LL z; update_path(x, y); break; } case 1: { int x = read(), y = read(); printf("%lld ", query_path(x, y)); break; } } } return 0; }