QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #544119 | #6253. Appeal to the Audience | _JF_ | TL | 8ms | 39684kb | C++14 | 1.3kb | 2024-09-02 09:46:50 | 2024-09-02 09:46:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N =1e6+10;
#define int long long
vector<int> g[N];
int n,k,ans,dep[N],depMax[N],hvs[N],top[N],c[N],a[N],fa[N];
struct node{
int Len,id;
}A[N];
bool cmp(node a,node b){
return a.Len<b.Len;
}
void dfs(int u,int fath){
dep[u]=dep[fath]+1,fa[u]=fath;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(v==fath) continue;
dfs(v,u);
if(depMax[v]>depMax[u]) depMax[u]=depMax[v],hvs[u]=v;
}
depMax[u]++;
for(int i=0;i<g[u].size();i++){
int v=g[u][i]; if(v==fath) continue;
if(hvs[u]==v) top[v]=u;
else top[v]=v;
}
}
void Slove(int u,int fath,int val){
if(g[u].size()==1) c[u]=val;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(v==fath) continue;
Slove(hvs[u],u,val);
}
}
void rdfs(int u,int fath){
for(int i=0;i<g[u].size();i++){
int v=g[u][i]; if(v==fath) continue;
rdfs(v,u);
c[u]=max(c[u],c[v]);
}
if(u!=1) ans+=c[u];
}
signed main(){
cin>>n>>k;
for(int i=1;i<=k;i++) cin>>a[i];
for(int i=1,x;i<n;i++) cin>>x,x++,g[i+1].push_back(x),g[x].push_back(i+1);
dfs(1,0),top[1]=1;
for(int i=1;i<=n;i++) if(top[i]==i) A[i].Len=depMax[i],A[i].id=i;
sort(A+1,A+n+1,cmp),sort(a+1,a+k+1);
for(int i=n,p=k,j=1;j<=k;i--,j++,p--) Slove(A[i].id,fa[A[i].id],a[p]);
rdfs(1,0);
cout<<ans<<endl;
return 0;
}
/*
5 3
5 4 3
0 0 1 1
*/
详细
Test #1:
score: 100
Accepted
time: 8ms
memory: 39468kb
input:
5 3 5 4 3 0 0 1 1
output:
17
result:
ok single line: '17'
Test #2:
score: 0
Accepted
time: 3ms
memory: 39684kb
input:
11 7 30 5 15 1 3 100 50 0 0 1 0 2 5 2 5 5 1
output:
454
result:
ok single line: '454'
Test #3:
score: -100
Time Limit Exceeded
input:
99999 50000 776281622 281552176 560818893 743574034 28371581 29065388 861522831 399277410 127891403 337521653 333045937 201722127 532376484 866178821 488930207 533328467 280762095 777881963 698720876 926181033 678638871 483709812 805740065 609341704 534943664 598002301 497944186 842902577 127602924 ...