90分+玄学问题求助
查看原帖
90分+玄学问题求助
35871
ZigZagKmp楼主2020/5/29 10:13
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005
#define maxm 2000005
#define inf 0x3f3f3f3f
#define int long long
#define mod 1000000007
#define local
void file(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
template <typename Tp> void read(Tp &x){
	int fh=1;char c=getchar();x=0;
	while(c>'9'||c<'0'){if(c=='-'){fh=-1;}c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c&15);c=getchar();}x*=fh;
}
struct Edge{
	int f,t,w,nxt;
}edge[maxm];
int head[maxn],etot=1;
void add_edge(int f,int t,int w=0){edge[++etot]=(Edge){f,t,w,head[f]};head[f]=etot;}
int a[maxn];
int n,m;
int bl[maxn];
multiset<int>st[maxn];
int ans;
int merge(int x,int y){
	if(st[y].size()>st[x].size())swap(x,y);
	multiset<int>::iterator itx=(--st[x].end()),ity;
	if(!st[y].size())return x;
	for(ity=(--st[y].end());;ity--){
		if((*itx)<(*ity)){
			st[x].erase(itx);
			st[x].insert(*ity);
		}
		if(itx!=st[x].begin())itx--;
		if(ity==st[y].begin())break;
	}
	return x;
}
void dfs(int x){
	bl[x]=x;
	for(int i=head[x];i;i=edge[i].nxt){
		int y=edge[i].t;
		dfs(y);
		bl[x]=merge(bl[x],bl[y]);
	}
	st[bl[x]].insert(a[x]);
}
signed main(){
	#ifndef local
		file("");
	#endif
	read(n);
	for(int i=1;i<=n;i++)read(a[i]);
	for(int i=2,x;i<=n;i++){
		read(x);
		add_edge(x,i);
	}
	dfs(1);
	for(multiset<int>::iterator it=st[bl[1]].begin();it!=st[bl[1]].end();it++){
		ans+=(*it);
	}
	printf("%lld\n",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}

现在90,在#10,#11答案错误(链的部分分)。

另有一个玄学错误,在本机测试时第3个样例直接运行会RE(id=3221225477)且无输出,但是调试正常且有正确输出,并且用洛谷IDE运行也完全正常。

2020/5/29 10:13
加载中...