比赛 |
EYOI与SBOI开学欢乐赛14th |
评测结果 |
AAAAAAAAAA |
题目名称 |
盗取资料 |
最终得分 |
100 |
用户昵称 |
yrtiop |
运行时间 |
0.523 s |
代码语言 |
C++ |
内存使用 |
5.98 MiB |
提交时间 |
2022-10-24 19:23:42 |
显示代码纯文本
#include <bits/stdc++.h>
#define pb emplace_back
typedef long long ll;
const int maxn = 1e5 + 5;
int n,a[maxn];
ll f[maxn],ans,T,sum[maxn];
std::vector<int> G[maxn];
void dfs1(int u,int fa) {
sum[u] = a[u];
for(auto& v : G[u]) {
if(v == fa)continue ;
dfs1(v , u);
sum[u] += sum[v];
f[u] += f[v] + sum[v];
}
return ;
}
void dfs2(int u,int fa) {
ans = std::min(ans , f[u]);
for(auto& v : G[u]) {
if(v == fa)continue ;
f[v] += (f[u] - f[v] - sum[v]) + sum[u] - sum[v];
sum[v] = sum[u];
dfs2(v , u);
}
return ;
}
int main() {
freopen("dqzl.in","r",stdin);
freopen("dqzl.out","w",stdout);
scanf("%d %lld",&n,&T);
for(int i = 1;i <= n;++ i)
scanf("%d",&a[i]);
for(int i = 1;i < n;++ i) {
int u,v;
scanf("%d %d",&u,&v);
G[u].pb(v);
G[v].pb(u);
}
ans = 1e16;
dfs1(1 , 0);
dfs2(1 , 0);
if(ans > T)puts("Poor Van");
else printf("%lld\n",ans);
return 0;
}