fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4. typedef long long int ll;
  5. const int size=2e5+5;
  6. vector <int> g[size];
  7. ll sum[size]={0},res=0,cost[size]={0},ans[size]={0};
  8. void dfs(int src,int par=-1,int dist=0)
  9. {
  10. 	res += 1LL*dist*cost[src];
  11. 	sum[src] = cost[src];
  12. 	for(int i:g[src])
  13. 	{
  14. 		if(i==par)
  15. 		continue;
  16. 		dfs(i,src,dist+1);
  17. 		sum[src] += sum[i];
  18. 	}
  19. }
  20. void dfs2(int src,int par=-1)
  21. {	ans[src] = res;
  22. 	for(auto i:g[src]){
  23. 		if (i==par) 
  24. 		continue;
  25. 		res -= sum[i];
  26. 		sum[src] -= sum[i];
  27. 		res += sum[src];
  28. 		sum[i] += sum[src];
  29. 		dfs2(i,src);
  30. 		sum[i] -= sum[src];
  31. 		res -= sum[src];
  32. 		sum[src] += sum[i];
  33. 		res += sum[i];
  34. 	}
  35. }
  36. int main()
  37. {
  38. 	ios_base::sync_with_stdio(false);
  39. 	cin.tie(NULL);
  40. 	ll n,q,a,b;
  41. 	cin>>n;
  42. 	for(int i=0,u,v;i<n-1;i++)
  43. 	cin>>u>>v,g[u].push_back(v),g[v].push_back(u);
  44. 	for(int i=1;i<=n;i++)
  45. 	cin>>cost[i];
  46. 	cin>>q;
  47. 	dfs(1);
  48. 	dfs2(1);
  49. 	while(q--)
  50. 	{
  51. 		cin>>a>>b;
  52. 		if(ans[a]<ans[b])
  53. 		cout<<"Amit\n";
  54. 		else if(ans[b]<ans[a])
  55. 		cout<<"Debasish\n";
  56. 		else
  57. 		cout<<"Both\n";
  58. 	}
  59. }
Time limit exceeded #stdin #stdout 5s 5267456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YKDy8i
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

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!