fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. typedef long long int ll;
  4.  
  5.  
  6. using namespace std;
  7.  
  8. ll mod = 998244353;
  9.  
  10. 	vector<ll> s;
  11. 	vector<ll> dp;
  12.     vector<ll> arr;
  13.  
  14. ll me(ll a,ll b,ll mod){
  15. 	ll x=1;
  16. 	a=a%mod;
  17.  
  18. 	while(b>0){
  19. 		if(b%2==1){
  20. 			x=(x*a)%mod;
  21. 		}
  22. 		a=(a*a)%mod;
  23. 		b=b/2;
  24. 	}
  25. 	return x;
  26. }
  27.  
  28. void dfs(int node , vector<vector<ll>> &g , vector<ll> &visited , vector<ll> &parent){
  29. 	visited[node]=1;
  30. 	for(auto &it : g[node]){
  31. 		if(visited[it]==0){
  32. 			parent[it]=node;
  33. 			dfs(it,g,visited,parent);
  34. 		}
  35. 	}
  36.  
  37. 	ll sum = 0;
  38. 	ll count =0;
  39.  
  40.  
  41. 	for(auto &it : g[node]){
  42. 		if(it != parent[node]){
  43. 		    count = count + dp[it];
  44. 			sum = sum + s[it];
  45. 		}
  46.  
  47. 	}
  48.  
  49. 	if(arr[node]<0){
  50. 		dp[node]=1+count;
  51. 		s[node]=sum + abs(arr[node]);
  52. 	}
  53. 	else{
  54. 		dp[node]=count;
  55. 		s[node]=sum + abs(arr[node]);
  56.  
  57. 	}
  58. }
  59.  
  60. int main() {
  61. 	// your code goes here
  62.  
  63.  
  64. 	// Taking 0-based indexing
  65.  
  66.  
  67. 	ll n,u,v;
  68. 	cin>>n;
  69.  
  70. 	ll sum=0;
  71.  
  72. 	ll count = 0;
  73. 	ll ans = 0;
  74.  
  75. 	s.resize(n,0);
  76. 	dp.resize(n,0);
  77. 	arr.resize(n,0);
  78.  
  79.  
  80.  
  81. 	for(int i=0;i<n;i++){
  82. 		cin>>arr[i];
  83. 		if(arr[i]<0){
  84. 			count++;
  85. 		}
  86. 		sum=sum+abs(arr[i]);
  87. 	}
  88.  
  89. 	vector<vector<ll>> g(n);
  90. 	for(int i=0;i<n-1;i++){
  91. 		cin>>u>>v;
  92. 		g[u].push_back(v);
  93. 		g[v].push_back(u);
  94.  
  95. 	}
  96.  
  97. 	vector<ll> visited(n,0);
  98.  
  99. 	vector<ll> parent(n,-1);
  100.  
  101.  
  102.  
  103. 	dfs(0,g,visited,parent);
  104.  
  105.  
  106. 	if(count%2==0){
  107. 		cout<<(me(2,sum,mod))<<endl;
  108. 	}
  109. 	else{
  110. 		for(int i=0;i<n;i++){
  111. 			if(arr[i]<0){
  112. 				if((count-dp[i])%2==0){
  113. 					ll res = sum - s[i];
  114. 					ans = max(ans,res);
  115. 				}
  116.  
  117.  
  118. 				for(auto &it : g[i]){
  119. 					if(it!=parent[i]){
  120. 						if(dp[it]%2==0){
  121. 							ans = max(ans,s[it]);
  122. 						}
  123. 					}
  124. 				}
  125. 			}
  126. 		}
  127. 		cout<<me(2,ans,mod)<<endl;
  128.  
  129. 	}
  130. 	return 0;
  131. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
5
3 -2 -4 1 -1
0 1
0 2
1 3
1 4
stdout
copy 
1024
https://ideone.com/vWBCeJ
language:
C++14 (gcc 8.3)
created:
15 hours 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!