fork download
copy 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <math.h>
  4. #include <string.h>
  5. #include <time.h>
  6. #include <stdlib.h>
  7. #include <string>
  8. #include <bitset>
  9. #include <vector>
  10. #include <set>
  11. #include <map>
  12. #include <queue>
  13. #include <algorithm>
  14. #include <sstream>
  15. #include <stack>
  16. #include <iomanip>
  17. using namespace std;
  18. #define pb push_back
  19. #define mp make_pair
  20. typedef pair<int,int> pii;
  21. typedef long long ll;
  22. typedef double ld;
  23. typedef vector<int> vi;
  24. #define fi first
  25. #define se second
  26. #define fe first
  27. #define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
  28. #define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
  29. #define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
  30. #define es(x,e) (int e=fst[x];e;e=nxt[e])
  31. #define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
  32. #define SZ 666666
  33. int T,n,v,a[SZ]; Edg
  34. ll f[SZ],s[SZ];
  35. void dfs(int x,int fa=0)
  36. {
  37. 	f[x]=s[x]=0;
  38. 	for esb(x,e,b) if(b!=fa)
  39. 	{
  40. 		dfs(b,x); s[x]+=s[b]; f[x]+=f[b];
  41. 	}
  42. 	f[x]+=a[x];
  43. 	f[x]=max(f[x],-(ll)v);
  44. }
  45. void sol()
  46. {
  47. 	scanf("%d%d",&n,&v); M=0;
  48. 	for(int i=1;i<=n;++i) fst[i]=0;
  49. 	for(int i=1;i<=n;++i) scanf("%d",a+i);
  50. 	for(int i=1,a,b;i<n;++i)
  51. 		scanf("%d%d",&a,&b),adde(a,b);
  52. 	dfs(1); printf("%lld\n",f[1]);
  53. }
  54. int main()
  55. {
  56. 	scanf("%d",&T);
  57. 	while(T--) sol();
  58. }
Success #stdin #stdout 0s 36064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/EkupL2
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!