前置知识：线段树合并，可持久化线段树，边分治，可能会用到一点点虚树。

P4565

边分树神题啊。。。

题意

给定两棵边有边权的树 T1,T2T_1, T_2，结点数都为 nn。设 di(x)d_i(x) 表示第 ii 棵树上 xx 的带权深度，
求一组点对 (x,y)(x, y)，使得 d1(x)+d1(y)−d1(p)−d2(p′)d_1(x) + d_1(y) - d_1(p) - d_2(p') 最大，
其中 p,p′p, p' 分别代表 x,yx, y 在两树上的 LCALCA。为了方便，只需输出最大值。

题解

先考虑变换一下这个式子，设 disi(x,y)dis_i(x, y) 表示 (x,y)(x, y) 在第 ii 棵树上的距离。那么原式就等于 12(dis1(x,y)+d1(x)+d1(y)−2d2(p′)){1 \over 2}(dis_1(x, y) + d_1(x) + d_1(y) - 2d_2(p'))。
于是沿用通道那题的做法，在 T1T_1 上新建结点 i′i' 与 ii 连接，边权为 d1(i)d_1(i)，接着在 T2T_2 上枚举 p′p'，找出最长路就行了？！
很不幸，这道题的边权可以是负数。所以无法合并最长路。

于是换一种思路，考虑将 dis1(x,y)dis_1(x, y) 转化一下。将 T1T_1 边分治，在一次分治过程中，设 h(x)h(x) 表示 xx 到分治中心一侧的距离，答案变成了 p(x)+p(y)+d1(x)+d1(y)−2d2(p′)p(x) + p(y) + d_1(x) + d_1(y) - 2d_2(p')，设 valx=px+d1(x)val_x = p_x + d_1(x)，那么又变为 valx+valy−2d2(p′)val_x + val_y - 2d_2(p')。在 T2T_2 中建出当前分治块的虚树，然后枚举一下 p′p' 就行了。复杂度 O(nlog⁡2n)\mathcal{O}(n \log^2 n)。
然而，注意到 n⩽366666n \leqslant 366666，所以这种做法虽然简单，但如果实现不好就需要大量卡常。而事实上，我们也能给出更为优秀的做法。

考虑先枚举 p′p'，然后算它的子树在 T1T_1 中对答案的贡献。于是不得不提到一个科技，叫边分树。

边分树是由 nn 个长度为 O(log⁡n)\mathcal{O}(\log n) 的链合并而成的。而且是一棵二叉树。

想要构建出 nn 个链，一种方法就是：初始时建立 nn 个二叉链，每个都为空，称第 ii 个节点对应第 ii 条链。对树进行边分治，设 u,vu, v 为分治边 ee 的两端点，钦定 dep(u)<dep(v)dep(u) < dep(v)，将 uu 那一侧的所有点对应的二叉链底端的左儿子赋为 ee，将 vv 侧的所有点对应的二叉链底端的右儿子赋为 ee。然后进行下一次分治。

也就是说一条二叉链上的点都是原树的一条边。

当两个边分树合并时，其方法类似于线段树合并，这里就不细说。最后合并完 nn 个二叉链的边分树等同于边分治时边与边的关系树，并且也是一棵二叉树。

边分树最强的地方就是可以维护某些信息。回到这道题，先枚举 p′p'，这时递归它在 T2T_2 的儿子，每个儿子都维护一个它们的点集合并出来的边分树。在合并两个儿子的时候，可以顺便在合并时统计答案。思考 (x,y)(x, y) 在边分治时应该何时统计它们的答案，应该是 x,yx, y 在同一分治块时。对应到边分树上就是：到某一深度前，x,yx, y 的边分树左右儿子关系都相同，在这一深度时，左右儿子关系出现第一次不同。那么为了统计答案，边分树上每个节点维护：这个点代表连通块内 valval 的最大值。合并时，当前两个节点祖先左右儿子关系一定相同（类似线段树合并），答案不难统计。时间复杂度 O(nlog⁡n)\mathcal{O}(n \log n)。

代码：

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
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 8E5 + 5;
int n;
i64 d[2][N], val[N];
struct lsqxx {
  int head[N >> 1], nex[N], sz[N], ctot;
  struct E {
    int to, nxt;
    int dis;
  } edge[N];
  void add(int x, int y, int z) {
    edge[++ctot] = (E) {x, y, z};
    ++sz[x]; ++sz[y];
    nex[ctot] = head[x]; head[x] = ctot;
  }
} g[2];
i64 ans = -1E15;
int ftot, root[N], ld[N];
struct bfs {
  struct node {
    int ls, rs;
    i64 val;
  } t[N * 40];
  int merge(int x, int y, int rt) {
    if (!x || !y) return x | y;
    if (t[x].ls && t[y].rs) 
      ans = max(ans, t[t[x].ls].val + t[t[y].rs].val - 2 * d[1][rt]);
    if (t[x].rs && t[y].ls)
      ans = max(ans, t[t[x].rs].val + t[t[y].ls].val - 2 * d[1][rt]);
    t[x].val = max(t[x].val, t[y].val);
    t[x].ls = merge(t[x].ls, t[y].ls, rt);
    t[x].rs = merge(t[x].rs, t[y].rs, rt);
    return x;
  }
} t;
namespace bfz {
  int sz[N], dmx, m, root, dsum, dep[N], head[N], nex[N << 1], tot = 1;
  bool vis[N];
  struct E {int to, nxt, dis;} edge[N << 1];
  void add(int x, int y, int z) {
    edge[++tot] = (E) {x, y, z};
    nex[tot] = head[x]; head[x] = tot;
  }
  void rebuild(int x, int fa) {
    int tmp = 0, len = g[0].sz[x], last;
    for (int i = g[0].head[x]; i; i = g[0].nex[i]) {
      int v = g[0].edge[i].nxt, w = g[0].edge[i].dis;
      if (v == fa) continue;
      ++tmp; if (tmp == 1) {
        add(x, v, w); add(v, x, w);
        last = x;
      } else if (tmp == len - (x != 1)) {
        add(last, v, w); add(v, last, w);
      } else {
        ++m;
        add(m, last, 0); add(last, m, 0);
        last = m;
        add(v, m, w); add(m, v, w);
      }
    }
    for (int i = g[0].head[x]; i; i = g[0].nex[i]) {
      int v = g[0].edge[i].nxt, w = g[0].edge[i].dis;
      if (v != fa) {
        dep[v] = dep[x] + 1;
        d[0][v] = d[0][x] + w;
        rebuild(v, x);
      }
    }
  }
  void getroot(int x, int fa) {
    sz[x] = 1;
    for (int i = head[x]; i; i = nex[i]) {
      int v = edge[i].nxt;
      if (v == fa || vis[i >> 1]) continue;
      getroot(v, x); sz[x] += sz[v];
      int tmp = max(sz[v], dsum - sz[v]);
      if (dmx > tmp) {
        dmx = tmp;
        root = i;
      }
    }
  }
  void dfs(int x, int fa, i64 dis, bool typ) {
    if (x <= n) {
      val[x] = d[0][x] + dis;
      t.t[++ftot] = (bfs :: node) {0, 0, val[x]};
      if (!typ) t.t[ld[x]].ls = ftot;
      else t.t[ld[x]].rs = ftot;
      ld[x] = ftot;
    }
    for (int i = head[x]; i; i = nex[i]) {
      int v = edge[i].nxt, w = edge[i].dis;
      if (vis[i >> 1] || v == fa) continue;
      dfs(v, x, dis + w, typ);
    }
  }
  void solve(int x, int nsum) {
    dmx = 1E9; dsum = nsum; root = 0;
    getroot(x, 0); if (!root) return ;
    vis[root >> 1] = 1;
    int u = edge[root].to, v = edge[root].nxt, w = edge[root].dis;
    bool cnm = 0;
    if (dep[u] > dep[v]) swap(u, v), cnm = 1;
    dfs(u, v, 0, 0); dfs(v, u, w, 1);
    if (cnm) swap(u, v);
    solve(u, dsum - sz[v]); solve(v, sz[v]);
  }
  void solve() {
    m = n;
    rebuild(1, 0);
    solve(1, m);
  }
}
void dfs(int x, int fa) {
  for (int i = g[1].head[x]; i; i = g[1].nex[i]) {
    int v = g[1].edge[i].nxt, w = g[1].edge[i].dis;
    if (v == fa) continue;
    d[1][v] = d[1][x] + w;
    dfs(v, x);
    root[x] = t.merge(root[x], root[v], x);
  }
}
signed main(void) {
  ios :: sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
  cin >> n;
  for (int i = 0; i < 2; ++i) {
    for (int j = 1; j < n; ++j) {
      int u, v, w; cin >> u >> v >> w;
      g[i].add(u, v, w);
      g[i].add(v, u, w);
    }
  } 
  for (int i = 1; i <= n; ++i) ld[i] = root[i] = ++ftot;
  bfz :: solve(); 
  dfs(1, 0);
  for (int i = 1; i <= n; ++i) {
    ans = max(ans, 2 * (d[0][i] - d[1][i]));
  }
  cout << ans / 2 << '\n';
}
/*
类人群星闪耀时：
1. 初始 root 没开节点。
2. dmx=tmp 写成 tmp=dmx。
3. 没判 x=y 的情况。
4. 三度化建边忘记赋边权。
5. 根据 dep 交换 u, v 后忘记交换回来。
*/

CF757G

边分树练习题

题意

给定一棵 nn 个结点的树和一个长度为 nn 的排列 pp，边有边权。接下来有 mm 个操作，每个操作有两种类型：

  • 1 l r x 询问 ∑i=lrdis(pi,x)\sum\limits_{i = l}^r dis(p_i, x)。
  • 2 x，交换 px,px+1p_x, p_{x + 1}，满足 x<nx < n。

强制在线。

题解

看到路径问题，可以想到点分治。于是一个初步的做法就是，记 kpi=ik_{p_i} = i，建立一棵点分树，记 disxdis_x 为 xx 到分治中心的距离，点分树上每个点维护分治块内以 kik_i 为下标的，disidis_i 为值的动态开店权值线段树。但是这样时空复杂度都是 O(nlog⁡2n)\mathcal{O}(n \log^2 n)，这道题有点卡空间，不是很推荐。

考虑边分树，沿用暴力写挂的思路，可以研发出可持久化边分树。类似于主席树，先边分治一遍弄出每个点对应的二叉链，然后 rootiroot_i 在 rooti−1root_{i - 1} 的基础上合并上 pip_i 对应的二叉链即可。这里边分树每个结点维护的信息显然是分治块内 disdis（到分治边一侧的距离）之和。

这样在询问的时候，对于第一种操作，找到 xx 对应的二叉链，然后进行一个 queryquery，用 rootrroot_r 的答案减去 rootl−1root_{l - 1} 的答案就行了。对于第二种操作，可以发现，竟然这只会改变 rootxroot_x 这一棵可持久化边分树！所以找到 px+1p_{x + 1} 对应的二叉链，然后暴力重构一下 rootxroot_x 就行了。

代码：

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
#include <bits/stdc++.h>
#define big() (n >= 100000)
using namespace std;
using i64 = long long;
const int N = 6E5 + 5;
int n, q, pe[N];
vector <pair <int, int>> G[N];
int root[N << 1], ld[N << 1], tot;
struct bfs {
  struct node {
    int ls, rs;
    i64 sum, cnt;
  } t[N * 40];
  void insert(int x, i64 val, bool p) {
    t[++tot] = (node) {0, 0, val, 1};
    (!p ? t[ld[x]].ls : t[ld[x]].rs) = tot;
    ld[x] = tot;
  }
  int update(int p, int q) {
    int rt = ++tot; t[rt] = t[p];
    if (!q) return rt; //cnmd
    t[rt].sum += t[q].sum; t[rt].cnt += t[q].cnt;
    t[rt].ls = update(t[rt].ls, t[q].ls);
    t[rt].rs = update(t[rt].rs, t[q].rs);
    return rt;
  }
  i64 query(int p, int q) {
    if (!p || !q) return 0;
    i64 res = 0;
    if (t[p].ls && t[q].rs)
      res += t[t[p].ls].sum + t[t[p].ls].cnt * t[t[q].rs].sum;
    if (t[p].rs && t[q].ls)
      res += t[t[p].rs].sum + t[t[p].rs].cnt * t[t[q].ls].sum;
    return res + query(t[p].ls, t[q].ls) + query(t[p].rs, t[q].rs);
  }
} t;
i64 CCnt;
namespace bfz {
  int head[N << 1], nex[N << 2], dmx, dsum, m, tot = 1, dep[N << 1];
  bool vis[N << 1];
  struct E {int to, nxt, dis;} edge[N << 2];
  void add(int x, int y, int z) {
    edge[++tot] = (E) {x, y, z};
    nex[tot] = head[x]; head[x] = tot;
  }
  void rebuild(int x, int fa) {
    int tmp = 0, len = G[x].size(), last;
    for (auto [v, w] : G[x]) {
      if (v == fa) continue;
      ++tmp; if (tmp == 1) {
        add(x, v, w); add(v, x, w);
        last = x;
      } else if (tmp == len - (x != 1)) {
        add(last, v, w); add(v, last, w);
      } else {
        ++m;
        add(last, m, 0); add(m, last, 0);
        last = m;
        add(m, v, w); add(v, m, w);
      }
    }
    for (auto [v, w] : G[x]) if (v != fa)
      rebuild(v, x);
  }
  int sz[N << 1], root;
  void getroot(int x, int fa) {
    ++CCnt;
    sz[x] = 1;
    for (int i = head[x]; i; i = nex[i]) {
      int v = edge[i].nxt;
      if (vis[i >> 1] || v == fa) continue;
      getroot(v, x); sz[x] += sz[v];
      int tmp = max(sz[v], dsum - sz[v]);
      if (dmx > tmp) {
        dmx = tmp;
        root = i;
      }
    }
  }
  void dfs(int x, int fa, i64 dis, bool typ) {
    if (x <= n) 
      t.insert(x + n, dis, typ);
    for (int i = head[x]; i; i = nex[i]) {
      int v = edge[i].nxt, w = edge[i].dis;
      if (v == fa || vis[i >> 1]) continue;
      dfs(v, x, dis + w, typ);
    }
  }
  void solve(int x, int nsum) {
    dsum = nsum; dmx = 1E9; root = 0;
    getroot(x, 0); if (!root) return ;
    vis[root >> 1] = 1;
    int u = edge[root].to, v = edge[root].nxt, w = edge[root].dis;
    bool cnm = 0;
    if (dep[u] > dep[v]) swap(u, v), cnm = 1;
    dfs(u, v, 0, 0); dfs(v, u, w, 1);
    if (cnm) swap(u, v);
    solve(u, dsum - sz[v]); solve(v, sz[v]);
  }
  void prework(int x, int fa) {
    for (int i = head[x]; i; i = nex[i]) {
      int v = edge[i].nxt;
      if (v == fa) continue;
      dep[v] = dep[x] + 1;
      prework(v, x);
    }
  }
  void solve() {
    m = n;
    rebuild(1, 0);
    prework(1, 0);
    solve(1, m);
  }
}
signed main(void) {
  ios :: sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) cin >> pe[i];
  for (int i = 1; i < n; ++i) {
    int u, v, w; cin >> u >> v >> w;
    G[u].emplace_back(v, w);
    G[v].emplace_back(u, w);
  } for (int i = 1; i <= n; ++i) root[i + n] = ld[n + i] = ++tot;
  bfz :: solve();
  for (int i = 1; i <= n; ++i) 
    root[i] = t.update(root[i - 1], root[pe[i] + n]);
  i64 lastans = 0;
  for (int i = 1; i <= q; ++i) {
    i64 opt, x; cin >> opt;
    if (opt == 1) {
      i64 l, r; cin >> l >> r >> x;
      l ^= lastans;
      r ^= lastans;
      x ^= lastans;
      cout << (lastans = \
      (t.query(root[r], root[x + n]) - t.query(root[l - 1], root[x + n]))) << '\n';
      lastans %= (1 << 30);
    } else {
      cin >> x; x ^= lastans;
      swap(pe[x], pe[x + 1]);
      root[x] = t.update(root[x - 1], root[pe[x] + n]);
    }
  }
  return 0;
}