树链剖分板子

 1 const int N = 1e5 + 5;
 2 vector<int> g[N];
 3 int fa[N], dp[N], sz[N], son[N], top[N], dfn[N], to[N], cnt = 0, n;
 4 void dfs1(int u, int o) {
 5     fa[u] = o;
 6     sz[u] = 1;
 7     dp[u] = dp[o] + 1;
 8     for (int i = 0; i < g[u].size(); ++i) {
 9         int v = g[u][i];
10         if(v != o) {
11             dfs1(v, u);
12             sz[u] += sz[v];
13             if(sz[v] > sz[son[u]]) son[u] = v;
14         }
15     }
16 }
17 void dfs2(int u, int t) {
18     top[u] = t;
19     dfn[u] = ++cnt;
20     to[cnt] = u;
21     if(!son[u]) return ;
22     dfs2(son[u], t);
23     for (int i = 0; i < g[u].size(); ++i) {
24         int v = g[u][i];
25         if(v != fa[u] && v != son[u]) dfs2(v, v);
26     }
27 }
28 void add(int u, int v, int x) {
29     int fu = top[u], fv = top[v];
30     while(fu != fv) {
31         if(dp[fu] >= dp[fv]) update(dfn[fu], dfn[u], x, 1, 1, n), u = fa[fu], fu = top[u];
32         else update(dfn[fv], dfn[v], x, 1, 1, n), v = fa[fv], fv = top[v];
33     }
34     if(dfn[u] <= dfn[v]) update(dfn[u], dfn[v], x, 1, 1, n);
35     else update(dfn[v], dfn[u], x, 1, 1, n);
36 }
37 int sum(int u, int v) {
38     int ans = 0, fu = top[u], fv = top[v];
39     while(fu != fv) {
40         if(dp[fu] >= dp[fv]) ans += query(dfn[fu], dfn[u], 1, 1, n), u = fa[fu], fu = top[u];
41         else ans += query(dfn[fv], dfn[v], 1, 1, n), v = fa[fv], fv = top[v];
42     }
43     if(dfn[u] <= dfn[v]) ans += query(dfn[u], dfn[v], 1, 1, n);
44     else ans += query(dfn[v], dfn[u], 1, 1, n);
45     return ans;
46 }
47 int lca(int u, int v) {
48     int fu = top[u], fv = top[v];
49     while(fu != fv) {
50         if(dp[fu] >= dp[fv]) u = fa[fu], fu = top[u];
51         else v = fa[fv], fv = top[v];
52     }
53     if(dp[u] <= dp[v]) return u;
54     else v;
55 }