【UR #7】水题走四方
假的想法有很多。考虑一个对的想法，注意到不能直接往上走，所以每次一定是有一个人停留在上面然后放一个分身下去把子树里一部分点做完，然后接着往下走。不妨记 A 是一直停留在上面的人，B 是分身，那么每次 B 处理子树中最后一个叶子时 A 就可以开始走了。显然 B 走的最后一个叶子一定是子树中深度最大的叶子。有一个暴力的 dp，记 \(f_u\) 表示 A 走到了 \(u\) 这个点的最小代价，然后就可以 \(O(n^2)\) 地转移了。
假设上一个关键点是 \(u\)，走到了 \(v\)，把转移写出来后会发现有两种情况：
- \(u\) 和 \(v\) 中间最深的叶子深度大于等于 \(v\) 的深度。
- \(u\) 和 \(v\) 中间最深的叶子深度小于 \(v\) 的深度。
考虑分开看待这两种情况。第二种情况看上去更容易解决，这种情况下 \(u\) 和 \(v\) 中间最深的点深度也不超过 \(v\) 的深度，不妨考虑 \(v\) 的父亲 \(w\)，如果 \(w\) 有两个儿子，那么就不合法了，所以 \(w\) 只有 \(v\) 这一个儿子，注意到当 A 走到 \(w\) 的时候 B 已经到达目的地了，所以这时候不妨直接让 B 传过来一起走。那么这就相当于把 \(w\) 也变成了一个关键点。精炼一下，我们直接不做第二种转移了，改成如果父亲只有一个儿子，那么可以直接花一步走下去，这样正确性还是有保证的。
第一种情况就显得较为复杂了。看上去没什么好的优化方法，可是优秀的做法往往脱胎于看上去不怎么特别的性质。考虑这样一件事情：如果在处理最后一个叶子时，A 和 B 先同时走了一段路程在分开，我们发现把分开的那个点设为关键点一定是不劣的。我们记 \(d_u\) 表示 \(u\) 子树除去 \(v\) 子树的最大深度，将上面的性质用形式化的语言说出来，即对于 \(u\) 和 \(u\) 子树在 \(v\) 方向上的儿子 \(w\)，如果 \(d_u = d_w\)，那么把 \(w\) 设为关键点是不劣的。考虑用单调栈维护出 \(v\) 上方的若干条长度递增的链，那么只可能在这些链处转移，而由于长度递增的性质这样的链的数量是 \(O(\sqrt n)\) 级别的。所以可以优化至 \(O(n \sqrt{n})\)。
还能不能做到更优呢？把图画出来，自然想到能不能直接用单调栈的栈顶转移呢？答案是可以的，原因是这么做则由于 A 的路径本质没有变化且只有第一种转移，所以步数是相等的。所以现在转移量已经变成了 \(O(n)\)，我们只需要求出第一种情况的具体转移即可。
从叶子到根考虑，每次将一个子树接到父亲上，在这个过程中如果存在转移还未确定的点则一定是深度最大的点和它向上的一条链，我们可以维护出每个子树的链顶，然后在合并的时候确定转移。均摊复杂度是优秀的 \(O(n)\)。
const int N = 5e6 + 10;
const LL inf = 1e15;
int n, fa[N], deg[N];
int cnt[N], dm[N], dep[N];
int nxt[N], mv[N];
LL ds[N], f[N], ans = inf;
char s[N << 1];
int main() {
scanf("%d%s",&n,s + 1);
if(n == 1) {
puts("0");
return 0;
}
for(int i = 1, k = 0, u = 0; i <= n * 2; ++i) {
if(s[i] == '(') {
++k, fa[k] = u, u = k;
if(fa[k]) ++deg[fa[k]];
} else {
u = fa[u];
}
}
for(int i = 2; i <= n; ++i)
dep[i] = dep[fa[i]] + 1;
for(int i = n; i > 1; --i) {
if(!deg[i]) {
cnt[i] = 1;
dm[i] = ds[i] = dep[i];
}
int f = fa[i], df = dm[f];
dm[f] = max(dm[f], dm[i]),
ds[f] += ds[i], cnt[f] += cnt[i];
int u, v;
for(u = i; u && dep[u] <= df; u = nxt[u])
mv[u] = f;
for(v = nxt[f]; v && dep[v] <= dm[i]; v = nxt[v])
mv[v] = f;
nxt[f] = u + v;
}
for(int i = 2; i <= n; ++i) {
f[i] = inf;
int j = mv[i];
if(j) f[i] = min(f[i], f[j] + (ds[j] - ds[i]) - 1ll * dep[j] * (cnt[j] - cnt[i]));
if(deg[fa[i]] == 1) f[i] = min(f[i], f[fa[i]] + 1);
if(deg[i] == 0) ans = min(ans, f[i]);
}
printf("%lld\n",ans);
}