QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#138529 | #6514. Is it well known in Poland? | MaxBlazeResFire | WA | 1ms | 3604kb | C++14 | 1.3kb | 2023-08-11 21:38:34 | 2023-08-11 21:38:35 |
Judging History
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'