比赛 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;
}