一种用来合并子树中关于深度的信息的trick
重儿子定义为沿着重儿子走到的叶子深度最深。
一个节点的 $k$ 级祖先所在的重链长度不小于 $k$。
证明显然。
1. 记录重链长度 $len[u]$ 以及链头 $top[u]$。
2. 记录倍增数组 $fa[u][sz]$。
3. 记录每条重链的链头往上跳重链长度的祖先 $up[u][len]$ 以及往下走重链长度的儿子 $down[u][len]$。
4. 记录每一个数字最高位的 $1$ $highbit[n]$。
预处理部分 $O(nlogn)$
先要求 $u$ 的 $k$ 级祖先。$u$ 所在的重链长度不一定大于 $k$，所以无法通过 3 得到的数组 $O(1)$ 得到答案。
可以先用倍增数组往上跳 $2^{highbit[k]}$ 步，得到节点 $v$。
$v$ 为 $u$ 的 $2^{highbit[k]}$级祖先，那么这条重链长度不小于 $2^{highbit[k]}$。
就可以用 3 得到的数组 $O(1)$ 得到答案了。
#include <bits/stdc++.h> const int N = 3e5 + 7; int fa[N][20], n, son[N], len[N], sz[N], dep[N], highbit[N]; int top[N]; std::vector<int> vec[N]; void dfs1(int u, int pre) { sz[u] = dep[u] = dep[pre] + 1; fa[u][0] = pre; for (int i = 1; i < 20; i++) if (fa[u][i - 1]) fa[u][i] = fa[fa[u][i - 1]][i - 1]; else break; for (int v: vec[u]) { if (v == pre) continue; dfs1(v, u); if (sz[v] > sz[son[u]]) son[u] = v, sz[u] = sz[v]; } } void dfs2(int u, int tp) { top[u] = tp; len[u] = sz[u] - dep[tp] + 1; if (!son[u]) return; dfs2(son[u], tp); for (int v: vec[u]) if (v != fa[u][0] && v != son[u]) dfs2(v, v); } std::vector<int> up[N], down[N]; int query(int u, int k) { if (k > dep[u]) return 0; if (!k) return u; u = fa[u][highbit[k]]; k ^= 1 << highbit[k]; if (!k) return u; if (dep[u] - dep[top[u]] == k) return top[u]; if (dep[u] - dep[top[u]] > k) return down[top[u]][dep[u] - dep[top[u]] - k - 1]; return up[top[u]][k - dep[u] + dep[top[u]] - 1]; } int main() { scanf("%d", &n); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); vec[u].push_back(v); vec[v].push_back(u); } dfs1(1, 0); dfs2(1, 1); for (int i = 1; i <= n; i++) if (i == top[i]) { int l = 0, u = i; while (l++ < len[i] && u) u = fa[u][0], up[i].push_back(u); l = 0, u = i; while (l++ < len[i]) u = son[u], down[i].push_back(u); } for (int i = 1, bit = 1; i <= n; i++) { if ((i >> bit) & 1) bit++; highbit[i] = bit - 1; } int q; scanf("%d", &q); for (int ans = 0; q--; ) { int u, k; scanf("%d%d", &u, &k); u ^= ans, k ^= ans; printf("%d\n", ans = query(u, k)); } return 0; }
在 dsu on tree 里用了两个 $log$ 的写法卡过去了。其实它可以 $O(n)$ 解决。
暴力 dp。$f[u][i]$ 表示 $u$ 的子树中与自己距离为 $i$ 的节点个数。
$f[u][i] = \sum f[v][i - 1]$。这样 dp 是 $O(n^2)$ 的。
但是会发现，第一个和 $u$ 合并的儿子 $v$ 的信息，仅仅只是第二维移动一位。
考虑长链剖分，$O(1)$ 继承重儿子的信息，再和轻儿子暴力合并。
$O(1)$ 继承可以用指针实现。
每个点只会在作为轻儿子的链头时被合并，而且每个点只作为一条重链的轻儿子的链头，而合并的复杂度是 $O(len_v)$
所以总的复杂度是 $O(\sum len)$，也就是 $O(n)$
#include <bits/stdc++.h> const int N = 1e6 + 7; std::vector<int> vec[N]; int dp[N], len[N], son[N], ans[N], n; int *f[N], *cur = dp; void dfs1(int u, int fa) { for (int v: vec[u]) { if (v == fa) continue; dfs1(v, u); if (len[son[u]] < len[v]) son[u] = v; } len[u] = len[son[u]] + 1; } void dfs(int u, int fa) { if (son[u]) { f[son[u]] = f[u] + 1; dfs(son[u], u); ans[u] = ans[son[u]] + 1; } f[u][0] = 1; for (int v: vec[u]) { if (v == fa || v == son[u]) continue; f[v] = cur; cur += len[v]; dfs(v, u); for (int i = 1; i <= len[v]; i++) { f[u][i] += f[v][i - 1]; if (f[u][i] > f[u][ans[u]] || (f[u][i] == f[u][ans[u]] && i < ans[u])) ans[u] = i; } } if (f[u][ans[u]] == 1) ans[u] = 0; } int main() { scanf("%d", &n); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); vec[u].push_back(v); vec[v].push_back(u); } dfs1(1, 0); f[1] = cur; cur += len[1]; dfs(1, 0); for (int i = 1; i <= n; i++) printf("%d\n", ans[i]); return 0; }
当 $b$ 为 $a$ 的祖先时，答案为 $\sum_{dep[a] - dep[b] \leq k} size[a] - 1$ 这一部分很好求。
当 $a$ 为 $b$ 的祖先时，答案为 $\sum_{dep[b] - dep[a] \leq k} size[b] - 1$。
第一种做法，求出dfs序，再按 dep 和 sz 建一棵主席树。那么对于第二部分就是二维数点了。复杂度 $O(nlogn)$。
第二种做法，离线询问，考虑长链剖分，$f[u][i]$ 表示 $u$ 的子树中与 $u$ 距离为 $i$ 的 sz 之和。
$f[u][i] = \sum f[v][i - 1]$。求一下后缀和，再回答询问即可。
每次合并的时候要求后缀和只需要 $f[u][0] += f[v][0]$ 即可。
因为所有的 $f[v][i]$ 都是一个后缀和。$f[u][i + 1]$ 加上 $f[v][i]$ 已经加上了那部分的后缀和。所以只需要处理 $f[u][0]$。
#include <bits/stdc++.h> #define ll long long #define pii pair<int, int> #define fi first #define se second const int N = 3e5 + 7; int n, sz[N], son[N], len[N], q, dep[N]; ll dp[N << 1], *cur = dp, *f[N], ans[N]; std::vector<int> vec[N]; std::vector<std::pii> query[N]; void dfs1(int u, int fa) { dep[u] = dep[fa] + 1; sz[u] = 1; for (int v: vec[u]) { if (v == fa) continue; dfs1(v, u); sz[u] += sz[v]; if (len[son[u]] < len[v]) son[u] = v; } len[u] = len[son[u]] + 1; } void dfs(int u, int fa) { f[u][0] = sz[u] - 1; if (son[u]) { f[son[u]] = f[u] + 1; dfs(son[u], u); f[u][0] += f[son[u]][0]; } for (int v: vec[u]) { if (v == fa || v == son[u]) continue; f[v] = cur; cur += len[v]; dfs(v, u); for (int j = 0; j < len[v]; j++) f[u][j + 1] += f[v][j]; f[u][0] += f[v][0]; } for (auto p: query[u]) { int i = p.fi, k = p.se; ans[i] += 1LL * std::min(dep[u] - 1, k) * (sz[u] - 1); if (k >= len[u] - 1) ans[i] += f[u][1]; else ans[i] += f[u][1] - f[u][k + 1]; } } int main() { scanf("%d%d", &n, &q); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); vec[u].push_back(v); vec[v].push_back(u); } for (int i = 1; i <= q; i++) { int u, k; scanf("%d%d", &u, &k); query[u].push_back(std::pii(i, k)); } dfs1(1, 0); f[1] = cur; cur += len[1]; dfs(1, 0); for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]); }
$f[u][i]$ 表示 $u$ 的子树中与 $u$ 距离为 $i$ 点的个数。
$g[u][i]$ 表示 $u$ 的子树中的点对 与 其lca的距离为 $d$，其 $lca$ 与 $u$ 的距离为 $d-i$ 的点对数。
在 $u$ 的另一棵子树中取一个与 $u$ 距离为 $i$ 的点既可以和这些点对组成合法的三元组。（画图可知）
第一个式子的合并就是上面的了。
第二个式子合并就是 $g[u][i] = \sum g[v][i + 1] + f[u][i] * f[v][i - 1]$ 第一部分是直接继承儿子的，lca 不为 $u$，第二部分为 lca 为 $u$ 的情况。
每次就先统计答案，再进行合并。
#include <bits/stdc++.h> #define ll long long const int N = 1e5 + 7; std::vector<int> vec[N]; int n, len[N], son[N]; ll dp[N * 4], *f[N], *g[N], *cur = dp, ans; void dfs1(int u, int fa = 0) { for (int v: vec[u]) { if (v == fa) continue; dfs1(v, u); if (len[son[u]] < len[v]) son[u] = v; } len[u] = len[son[u]] + 1; } void dfs(int u, int fa) { if (son[u]) { f[son[u]] = f[u] + 1; g[son[u]] = g[u] - 1; dfs(son[u], u); } f[u][0] = 1; ans += g[u][0]; for (int v: vec[u]) { if (v == fa || v == son[u]) continue; f[v] = cur; cur += len[v] << 1; g[v] = cur; cur += len[v] << 1; dfs(v, u); for (int j = 0; j < len[v]; j++) { if (j) ans += f[u][j - 1] * g[v][j]; ans += f[v][j] * g[u][j + 1]; } for (int j = 0; j < len[v]; j++) { g[u][j + 1] += f[u][j + 1] * f[v][j]; if (j) g[u][j - 1] += g[v][j]; f[u][j + 1] += f[v][j]; } } } int main() { scanf("%d", &n); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); vec[u].push_back(v); vec[v].push_back(u); } dfs1(1); f[1] = cur; cur += len[1] << 1; g[1] = cur; cur += len[1] << 1; dfs(1, 0); printf("%lld\n", ans); return 0; }
cogs2652
求一条长度为 $m$ 的路径使得 $\dfrac{\sum a_i}{\sum b_i}$ 最小。
看到这个表达就想到 01分数规划，变成是否存在一条路径的 $\sum a_i - mid * b_i$ 小于 $0$。可以点分治。
$f[u][i]$ 表示 $u$ 的子树中与 $u$ 距离为 $i$ 的 $\sum a_i - mid * b_i$ 的最小值。
转移为 $f[u][i] = min{f[v][i - 1]} + a_i - mid * b_i$。发现有个偏移量，那么继承重儿子用一个数组记录偏移量，$f[u][i]$ 都减去重儿子的偏移量，更新的时候再加回来即可。
#include <bits/stdc++.h> const int N = 2e5 + 7; std::vector<int> vec[N]; int a[N], b[N], n, m, len[N], son[N]; double val[N], dp[N], *f[N], *cur = dp, ans = 1e18; void dfs1(int u, int fa) { for (int v: vec[u]) { if (v == fa) continue; dfs1(v, u); if (len[son[u]] < len[v]) son[u] = v; } len[u] = len[son[u]] + 1; } void dfs(int u, int fa, double mid) { val[u] = a[u] - mid * b[u]; f[u][0] = 0; if (son[u]) f[son[u]] = f[u] + 1, dfs(son[u], u, mid), val[u] += val[son[u]], f[u][0] -= val[son[u]]; for (int v: vec[u]) { if (v == fa || v == son[u]) continue; f[v] = cur; cur += len[v]; dfs(v, u, mid); for (int j = 0; j < len[v] && j < m; j++) if (m - j - 1 < len[u]) ans = std::min(ans, f[v][j] + val[v] + f[u][m - j - 1] + val[u]); for (int j = 0; j < len[v] && j < m; j++) f[u][j + 1] = std::min(f[u][j + 1], f[v][j] + val[v] - val[u] + a[u] - mid * b[u]); } if (m < len[u]) ans = std::min(ans, f[u][m] + val[u]); } int main() { scanf("%d%d", &n, &m); m--; for (int i = 1; i <= n; i++) scanf("%d", a + i); for (int i = 1; i <= n; i++) scanf("%d", b + i); for (int i = 1; i <= n; i++) ans = std::min(ans, 1.0 * a[i] / b[i]); if (m == 0) { printf("%.2f\n", ans); return 0; } for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); vec[u].push_back(v); vec[v].push_back(u); } dfs1(1, 0); double l = 0, r = N; for (int cnt = 0; cnt < 50; cnt++) { double mid = (l + r) / 2; memset(dp, 0x7f, sizeof(dp)); ans = 1e18; cur = dp; f[1] = cur; cur += len[1]; dfs(1, 0, mid); if (ans >= 0) l = mid; else r = mid; } if (l >= 200000) puts("-1"); else printf("%.2f\n", l); return 0; }
完结撒花！！！
原文：https://www.cnblogs.com/Mrzdtz220/p/11742061.html
