比赛 EYOI与SBOI开学欢乐赛14th 评测结果 AAAAAAAAAA
题目名称 盗取资料 最终得分 100
用户昵称 op_组撒头屯 运行时间 0.180 s
代码语言 C++ 内存使用 4.97 MiB
提交时间 2022-10-24 19:18:10
显示代码纯文本
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N=100000+5;
  5. const ll inf=0x3f3f3f3f3f3f;
  6. struct sdf{
  7. int to,next;
  8. }eg[2*N];
  9. int head[N],ne=0;
  10. int n;
  11. ll a[N],T;
  12. void add(int x,int y){
  13. eg[++ne]={y,head[x]};
  14. head[x]=ne;return ;
  15. }
  16. ll f[N],sz[N];
  17. void dfs1(int pt,int fa){
  18. for (int i=head[pt];i!=0;i=eg[i].next){
  19. int v=eg[i].to;
  20. if (v==fa)continue;
  21. dfs1(v,pt);
  22. sz[pt]+=sz[v];
  23. f[pt]+=f[v]+sz[v];
  24. }
  25. sz[pt]+=a[pt];
  26. return ;
  27. }
  28. void dfs2(int pt,int fa){
  29. for (int i=head[pt];i!=0;i=eg[i].next){
  30. int v=eg[i].to;
  31. if (v==fa)continue;
  32. f[v]=f[pt]+sz[1]-2*sz[v];
  33. dfs2(v,pt);
  34. }
  35. return ;
  36. }
  37. int main(){
  38. freopen ("dqzl.in","r",stdin);
  39. freopen ("dqzl.out","w",stdout);
  40. scanf("%d%lld",&n,&T);
  41. for (int i=1;i<=n;i++){
  42. scanf("%lld",&a[i]);
  43. }
  44. for (int i=1;i<n;i++){
  45. int x,y;scanf("%d%d",&x,&y);
  46. add(x,y);add(y,x);
  47. }
  48. dfs1(1,1);dfs2(1,1);
  49. ll ans=inf;
  50. for (int i=1;i<=n;i++)ans=min(ans,f[i]);
  51. if (ans>T)printf("Poor Van\n");
  52. else printf("%lld\n",ans);
  53. return 0;
  54. }
  55.