[传送门]
考虑计算直径的 dp 方法。
$d[u]$ 表示以 $u$ 为根的子树能 $u$ 能走到的最远距离
$dp[u]$ 表示以 $u$ 为根的子树的直径
那么每次dfs一个子节点后
$dp[u] = max(d[u] + d[v] + 1, dp[u])$
$d[u] = max(d[v] + 1, d[u])$
注意顺序一反就错了。
这里并没有考虑到 $u$ 是某个节点的儿子是，路径可以往父节点走的情况，但是这是对的。
因为如果这种情况存在，那么我们在递归回父节点是就可以更新到。所以直径取最后 dp 数组的最大值是对的。
回到这个题，因为数据的生成方式，树高不超过 $log n$，并且第 $i$ 条边一定有 第 $i + 1$个节点。
如果从 $[x, n - 1]$ 这棵树已经建好了，那么加入第 $x - 1$ 条边就是把 $p[x - 1]$ 和 $x$ 这两个节点形成的连通块进行合并。
深度不超过 $log n$，那么可以暴力一点。
将询问离线。按 $r$ 从大到小排序，考虑倒序建这棵树。
$f[u][i]$ 表示以 $u$ 为根的子树内 $u$ 能到达的最远距离为 $i$ 时 $r$ 的最小值。即在 $[l, f[u][i]]$ $u$ 能往下走 $i$ 步。
$g[i]$ 表示树的直径至少为 $i$ 时 最小的 $r$。即在 $[l, g[i]]$ 树的直径至少为 $i$。
倒序加入一条边，相当于两棵树合并，那么就先更新 $g$ 数组，具体更新方式如 $dp$ 的更新方式，分别枚举高度进行合并。
$g[i + j + 1] = min(g[i + j + 1], max(f[u][i], f[v][i], v - 1))$ $v-1$ 即为当前加入的边。
在更新 $u$，即 $u$ 为 $v$ 的父亲。
$f[u][i] = min(f[u][i], max(f[v][i - 1], v - 1))$
求答案就枚举高度看 $g$ 数组是否小于当前 $r$
#include <bits/stdc++.h> using namespace std; const int N = 5e5 + 7; const int dep = 40; struct In { int l, r; bool operator < (const In &rhs) const { if (l == rhs.l) return r > rhs.r; return l > rhs.l; } } que[N]; int f[N][dep + 7]; int g[dep * 3]; int p[N], n; void add(int u, int v) { for (int i = 0; i < dep; i++) if (f[u][i] < n) for (int j = 0; j < dep; j++) g[i + j + 1] = min(g[i + j + 1], max(f[u][i], max(f[v][j], v - 1))); for (int i = 1; i < dep; i++) f[u][i] = min(f[u][i], max(f[v][i - 1], v - 1)); } int main() { scanf("%d", &n); memset(f, 0x3f, sizeof(f)); for (int i = 1, x; i < n; i++) scanf("%d%d", p + i, &x), f[i][0] = 0; f[n][0] = 0; memset(g, 0x3f, sizeof(g)); int q; scanf("%d", &q); for (int i = 1; i <= q; i++) scanf("%d%d", &que[i].l, &que[i].r); sort(que + 1, que + 1 + q); int now = n - 1; int ans = 0; for (int i = 1; i <= q; i++) { while (now && now >= que[i].l) { add(p[now], now + 1); now--; } for (int k = dep * 2; k >= 0; k--) { if (g[k] <= que[i].r) { ans += k; break; } } } printf("%d\n", ans); return 0; }
原文：https://www.cnblogs.com/Mrzdtz220/p/11664638.html
