[十二省联考 2019] 春节十二响
感觉作为例题还是挺不错的。
感官上直接分析比较困难。不妨先考虑怎样的段长集合是合法的。
注意到合法等价于对每一条从根到叶子的链都合法，考虑在链上贪心，尝试将每个和比他大的最小的点做匹配，如果能匹配上就是合法。很显然，如果仅考虑一条链，那么极小的一个合法段长集合就是这条链的点权集合。这启发我们考虑将每一条这样的根到叶子的链的答案合并，每次贪心取两者最大值即可。这样就获得了一个 \(O(n^2\log n)\) 的做法。
考虑优化这个过程，首先每条链的对应集合可以放到 DFS 的过程中去做，但是这样做不了。利用 dp 的思想，记 \(S_u\) 表示以 \(u\) 为根的子树对应的集合，那么每次转移合并子树即可。注意到合并的复杂度和深度有关，那么来个长链剖分就变成线性的了。算上堆的复杂度就是 \(O(n \log n)\)。
const int N = 2e5 + 10;
int n, a[N];
vector<int> G[N];
int dep[N];
priority_queue<int> s[N];
void dfs(int u) {
int t = 0;
for(int v : G[u]) {
dfs(v);
if(dep[v] > dep[t]) t = v;
}
dep[u] = dep[t] + 1;
swap(s[u], s[t]);
for(int v : G[u]) {
if(v == t) continue;
vector<int> buf;
for(int k = 1; k <= dep[v]; ++k) {
int w = s[v].top(); s[v].pop();
int c = s[u].top(); s[u].pop();
buf.emplace_back(max(w, c));
}
for(int x : buf) s[u].push(x);
}
s[u].push(a[u]);
}
int main() {
read(n);
for(int i = 1; i <= n; ++i)
read(a[i]);
for(int i = 2; i <= n; ++i) {
int x; read(x);
G[x].emplace_back(i);
}
dfs(1);
LL ans = 0;
while(s[1].size()) {
ans += s[1].top();
s[1].pop();
}
printf("%lld\n",ans);
}