QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#138529#6514. Is it well known in Poland?MaxBlazeResFireWA 1ms3604kbC++141.3kb2023-08-11 21:38:342023-08-11 21:38:35

Judging History

你现在查看的是最新测评结果

  • [2023-08-11 21:38:35]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3604kb
  • [2023-08-11 21:38:34]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,head[100005],tot,x,y,ind,oo;
long long a[100005],sum[100005],dp[100005],cnt[100005],tmpp;
struct stu{
	int to;
	int nxt;
}w[400005];
struct stuu{
	long long val;
	int indd;
}tmp[100005];
bool cmp(stuu aa,stuu bb){
	return aa.val>bb.val;
}
void ade(int xx,int yy){
	w[++tot].to=yy;
	w[tot].nxt=head[xx];
	head[xx]=tot;
}
void dfss(int cyf,int fa){
	sum[cyf]=a[cyf];
	for(int i=head[cyf];i;i=w[i].nxt){
		if(w[i].to==fa)
			continue;
		cnt[cyf]++;
		dfss(w[i].to,cyf);
		sum[cyf]+=sum[w[i].to];
	}
}
void dfs(int cyf,int fa){
	if(cnt[cyf]==0)
		dp[cyf]=a[cyf];
	else{
		for(int i=head[cyf];i;i=w[i].nxt){
			if(w[i].to==fa)
				continue;
			dfs(w[i].to,cyf);
		}
		dp[cyf]=a[cyf];
		ind=0;
		for(int i=head[cyf];i;i=w[i].nxt){
			if(w[i].to==fa)
				continue;
			tmp[++ind].val=dp[w[i].to];
			tmp[ind].indd=w[i].to;
		}
		sort(tmp+1,tmp+1+ind,cmp);
		oo=0;
		for(int i=1;i<=ind;i++){
			if(oo==0)
				tmpp=sum[tmp[i].indd]-tmp[i].val;
			else
				tmpp=tmp[i].val;
			dp[cyf]+=tmpp;
			oo^=1;
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<n;i++){
		cin>>x>>y;
		ade(x,y);
		ade(y,x);
	}
	dfss(1,-1);
	dfs(1,-1);
	cout<<dp[1]<<endl;
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3604kb

input:

5
1 5 3 2 4
1 2
1 3
2 4
2 5

output:

8

result:

wrong answer 1st numbers differ - expected: '7', found: '8'