哪位大佬帮忙看一下
拜托了
by 光明正大 @ 2019-04-12 23:57:39
我告诉你
by 渺小的Mastar @ 2019-04-13 00:12:58
@[光明正大](/space/show?uid=121563) 你把swap交换的换成两个下标就好了
具体可以可以看我的代码
by 渺小的Mastar @ 2019-04-13 00:19:12
```cpp
#include<queue>
#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
#define rgi register int
#define rgu register unsigned int
using namespace std;
typedef long long ll;
const ll MAXN=200005;
int M[MAXN],ttt,k,id[MAXN];
inline int read()
{
int x=0,f=1;
char c=getchar();
for(;!isdigit(c);c=getchar())
if(c=='-')f=-1;
for(;isdigit(c);c=getchar())
x=(x<<3)+(x<<1)+c-'0';
return x*f;
}
vector<int>v,vec[MAXN];
priority_queue<int>que[MAXN];
inline void merge(int father,int child)
{
if(que[id[father]].size()<que[id[child]].size())
swap(id[father],id[child]);
while(que[id[child]].size())
{
v.push_back(max(que[id[father]].top(),que[id[child]].top()));
que[id[father]].pop(),que[id[child]].pop();
}
while(v.size())que[id[father]].push(v.back()),v.pop_back();
}
inline void dfs(int x)
{
id[x]=++ttt;
for(rgu i=0;i<vec[x].size();++i)
{
dfs(vec[x][i]);
merge(x,vec[x][i]);
}
que[id[x]].push(M[x]);
}
int main()
{
int fi,n=read();
for(rgi i=1;i<=n;++i)
M[i]=read();
for(rgi i=2;i<=n;++i)
vec[read()].push_back(i);
ll ans=0;
dfs(1);
while(que[id[1]].size())ans+=que[id[1]].top(),que[id[1]].pop();
printf("%lld\n",ans);
return 0;
}
```
by 渺小的Mastar @ 2019-04-13 00:19:29
得写启发式合并啊
by _虹_ @ 2019-04-13 06:54:44
哦
谢谢，改成id[]的样子就过了
但这是为什么？
by 光明正大 @ 2019-04-13 23:47:29
@[光明正大](/space/show?uid=121563) 你怎么写的和提接一模一样
by ecnerwaIa @ 2019-04-16 10:43:25
好歹自己想一下啊
by ecnerwaIa @ 2019-04-16 10:44:18
@[光明正大](/user/121563) 开C++11
by lnwsh @ 2021-07-02 11:12:56