题解 P5290 【[十二省联考2019]春节十二响】
Owen_codeisking
2019-04-07 17:50:51
不知道别人怎么写的，所以来讲一讲我自己的心路历程。
### $n\leq 2000$
可以贪心。先按权值从大到小排序，然后依次判一个点是否包含一个点。若没有包含关系，就直接加入集合中。
那怎么判一个点 $x$ 是否另一个点 $y$ 存在包含关系呢？$(a_x>a_y)$
1. $x$ 在 $y$ 的子树中，即 $st_y\leq id_x\leq ed_y$，开一个单点加区间查的树状数组即可。
2. $y$ 在 $x$ 的子树中，即 $st_x\leq id_y\leq ed_x$，开一个区间加单点查的树状数组即可。
时间复杂度 $O(n^2\log n)$
因为实际上常数根本跑不满，所以 $n\leq 2000$ 可以随便过。
### 树是一条链（$1$ 不一定是链的端点）
其实链的部分分已经提示你正解了。
容易发现 $1$ 最多有两个支链，所以我们暴力找出这两条链的所有权值，然后 $sort$ 一下，将两条支链对应的权值相加即可。
时间复杂度 $O(n\log n)$
### 正解
借鉴目前 $loj$ 最优解 $relyt871$ 的思路。
其实链的部分分已经提示你可以尝试合并两个集合的最大值了。
我们对于每个点都开一个堆，每次将 $siz$ 较小的合并到 $siz$ 较大的堆中。
因为每个点只会被合并 $\log n$ 次，时间复杂度 $O(n\log^2 n)$
$Upd$：时间复杂度 $O(n\log n)$
[$loj$ 评测记录证明只 $merge$ 了 $n$ 次](https://loj.ac/submission/409771)
$Code\ Below:$
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=200000+10;
int n,a[maxn],fa[maxn],tmp[maxn],id[maxn],tim;
int head[maxn],to[maxn],nxt[maxn],tot;
priority_queue<int> q[maxn];
inline int read()
{
register int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
inline void addedge(int x,int y)
{
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void dfs(int x)
{
id[x]=++tim;
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];dfs(y);
if(q[id[x]].size()<q[id[y]].size()) swap(id[x],id[y]);
int m=q[id[y]].size();
for(int i=1;i<=m;i++)
{
tmp[i]=max(q[id[x]].top(),q[id[y]].top());
q[id[x]].pop();q[id[y]].pop();
}
for(int i=1;i<=m;i++) q[id[x]].push(tmp[i]);
}
q[id[x]].push(a[x]);
}
int main()
{
n=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=2;i<=n;i++) fa[i]=read(),addedge(fa[i],i);
dfs(1);
ll ans=0;
while(!q[id[1]].empty()) ans+=q[id[1]].top(),q[id[1]].pop();
printf("%lld\n",ans);
return 0;
}
```
暴力的 $code$ 就不给啦，有兴趣去我 $loj$ 的提交记录上看好了。