前置知识：线段树合并，可持久化线段树，边分治，可能会用到一点点虚树。
P4565
边分树神题啊。。。
题意
给定两棵边有边权的树 \(T_1, T_2\)，结点数都为 \(n\)。设 \(d_i(x)\) 表示第 \(i\) 棵树上 \(x\) 的带权深度，
求一组点对 \((x, y)\)，使得 \(d_1(x) + d_1(y) - d_1(p) - d_2(p')\) 最大，
其中 \(p, p'\) 分别代表 \(x, y\) 在两树上的 \(LCA\)。为了方便，只需输出最大值。
题解
先考虑变换一下这个式子，设 \(dis_i(x, y)\) 表示 \((x, y)\) 在第 \(i\) 棵树上的距离。那么原式就等于 \({1 \over 2}(dis_1(x, y) + d_1(x) + d_1(y) - 2d_2(p'))\)。
于是沿用通道那题的做法，在 \(T_1\) 上新建结点 \(i'\) 与 \(i\) 连接，边权为 \(d_1(i)\)，接着在 \(T_2\) 上枚举 \(p'\)，找出最长路就行了？！
很不幸，这道题的边权可以是负数。所以无法合并最长路。
于是换一种思路，考虑将 \(dis_1(x, y)\) 转化一下。将 \(T_1\) 边分治，在一次分治过程中，设 \(h(x)\) 表示 \(x\) 到分治中心一侧的距离，答案变成了 \(p(x) + p(y) + d_1(x) + d_1(y) - 2d_2(p')\)，设 \(val_x = p_x + d_1(x)\)，那么又变为 \(val_x + val_y - 2d_2(p')\)。在 \(T_2\) 中建出当前分治块的虚树，然后枚举一下 \(p'\) 就行了。复杂度 \(\mathcal{O}(n \log^2 n)\)。
然而，注意到 \(n \leqslant 366666\)，所以这种做法虽然简单，但如果实现不好就需要大量卡常。而事实上，我们也能给出更为优秀的做法。
考虑先枚举 \(p'\)，然后算它的子树在 \(T_1\) 中对答案的贡献。于是不得不提到一个科技，叫边分树。
边分树
边分树是由 \(n\) 个长度为 \(\mathcal{O}(\log n)\) 的链合并而成的。而且是一棵二叉树。
想要构建出 \(n\) 个链，一种方法就是：初始时建立 \(n\) 个二叉链，每个都为空，称第 \(i\) 个节点对应第 \(i\) 条链。对树进行边分治，设 \(u, v\) 为分治边 \(e\) 的两端点，钦定 \(dep(u) < dep(v)\)，将 \(u\) 那一侧的所有点对应的二叉链底端的左儿子赋为 \(e\)，将 \(v\) 侧的所有点对应的二叉链底端的右儿子赋为 \(e\)。然后进行下一次分治。
也就是说一条二叉链上的点都是原树的一条边。
当两个边分树合并时，其方法类似于线段树合并，这里就不细说。最后合并完 \(n\) 个二叉链的边分树等同于边分治时边与边的关系树，并且也是一棵二叉树。
边分树最强的地方就是可以维护某些信息。回到这道题，先枚举 \(p'\)，这时递归它在 \(T_2\) 的儿子，每个儿子都维护一个它们的点集合并出来的边分树。在合并两个儿子的时候，可以顺便在合并时统计答案。思考 \((x, y)\) 在边分治时应该何时统计它们的答案，应该是 \(x, y\) 在同一分治块时。对应到边分树上就是：到某一深度前，\(x, y\) 的边分树左右儿子关系都相同，在这一深度时，左右儿子关系出现第一次不同。那么为了统计答案，边分树上每个节点维护：这个点代表连通块内 \(val\) 的最大值。合并时，当前两个节点祖先左右儿子关系一定相同（类似线段树合并），答案不难统计。时间复杂度 \(\mathcal{O}(n \log n)\)。
代码
#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
边分树练习题
题意
给定一棵 \(n\) 个结点的树和一个长度为 \(n\) 的排列 \(p\)，边有边权。接下来有 \(m\) 个操作，每个操作有两种类型：
1 l r x询问 \(\sum\limits_{i = l}^r dis(p_i, x)\)。2 x，交换 \(p_x, p_{x + 1}\)，满足 \(x < n\)。
强制在线。
题解
看到路径问题，可以想到点分治。于是一个初步的做法就是，记 \(k_{p_i} = i\)，建立一棵点分树，记 \(dis_x\) 为 \(x\) 到分治中心的距离，点分树上每个点维护分治块内以 \(k_i\) 为下标的，\(dis_i\) 为值的动态开店权值线段树。但是这样时空复杂度都是 \(\mathcal{O}(n \log^2 n)\)，这道题有点卡空间，不是很推荐。
考虑边分树，沿用暴力写挂的思路，可以研发出可持久化边分树。类似于主席树，先边分治一遍弄出每个点对应的二叉链，然后 \(root_i\) 在 \(root_{i - 1}\) 的基础上合并上 \(p_i\) 对应的二叉链即可。这里边分树每个结点维护的信息显然是分治块内 \(dis\)（到分治边一侧的距离）之和。
这样在询问的时候，对于第一种操作，找到 \(x\) 对应的二叉链，然后进行一个 \(query\)，用 \(root_r\) 的答案减去 \(root_{l - 1}\) 的答案就行了。对于第二种操作，可以发现，竟然这只会改变 \(root_x\) 这一棵可持久化边分树！所以找到 \(p_{x + 1}\) 对应的二叉链，然后暴力重构一下 \(root_x\) 就行了。
代码
#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;
}