QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #408840 | #6538. Lonely King | Doqe | WA | 1ms | 3604kb | C++23 | 795b | 2024-05-11 08:56:17 | 2024-05-11 08:56:19 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>to[N];
int fa[N],v[N],ban[N],p[N],n;
long long ans=0;
int dfs(int u)
{
if(!to[u].size())return v[u];
int w=0;for(int v:to[u])w+=dfs(v);
if(u==1||to[u].size()>1)ans+=1ll*v[u]*w;return w;
}
int main()
{
cin>>n;if(n==1)return puts("0"),0;
for(int i=2;i<=n;++i)cin>>fa[i],to[fa[i]].push_back(i);
for(int i=1;i<=n;++i)cin>>v[i];
dfs(1);//cerr<<ans<<endl;
ans=0;
for(int i=1;i<=n;++i)p[i]=i;
sort(p+1,p+n+1,[=](int x,int y){return v[x]<v[y];});
for(int _=1;_<=n;++_)
{
int u=p[_];long long w=v[u];
if(to[u].size())continue;
while(u!=1&&!ban[u])
{
ban[u]=1;
if(to[u].size()>1)ans+=v[u]*w;
u=fa[u];
}
if(to[u].size()>1||u==1)ans+=v[u]*w;
}
cout<<ans<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3604kb
input:
4 1 1 2 2 1 3 2
output:
10
result:
ok 1 number(s): "10"
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3600kb
input:
50 1 2 1 1 2 1 6 3 7 5 11 11 8 10 7 8 9 7 17 2 18 4 23 8 17 21 3 19 2 4 21 18 1 26 21 36 26 24 7 7 29 27 19 29 36 11 29 42 21 15 31 15 40 15 33 2 33 15 6 50 48 33 6 43 36 19 37 28 32 47 50 8 26 50 44 50 31 32 44 22 15 46 11 33 38 22 27 43 29 8 1 21 31 28 26 39 29 39 42
output:
35519
result:
wrong answer 1st numbers differ - expected: '22728', found: '35519'