fork download
copy 
  1. //#include<bits/stdc++.h>
  2. #include<vector>
  3. #include<iostream>
  4. #include<algorithm>
  5. #define ll long long
  6. #define ldb long double
  7. #define fi first
  8. #define se second
  9. #define sza(a) (int)a.size()
  10. #define pir pair<int,int>
  11. #define pirll pair<ll,ll>
  12. using namespace std;
  13. const int maxn = 2e5 + 5;
  14.  
  15. template <typename T> void maxi(T &x,T y){if (x < y) x = y;}
  16.  
  17. struct tree{
  18. 	int D[maxn],sz[maxn];
  19. 	ll R[maxn],V[maxn][2],child_cost[maxn],dp[maxn],maxR = 0;
  20. 	vector<int> vec[maxn];
  21.  
  22. 	void add_edge(int u,int v){
  23. 		vec[u].push_back(v);
  24. 		vec[v].push_back(u);
  25. 	}
  26.  
  27. 	void init_dfs(int u,int par){
  28. 		sz[u] = 1;
  29. 		if (u == 1) D[u] = 1;
  30.  
  31. 		for (int v : vec[u])
  32. 		  if (v != par){
  33. 		  	D[v] = D[u] + 1;
  34. 		  	init_dfs(v,u);
  35. 		  	sz[u] += sz[v];
  36. 		  }
  37. 	}
  38.  
  39. 	ll calc_self_cost(int n){
  40. 		ll cost = 0;
  41. 		for (int u = 1 ; u <= n ; u++)
  42. 		   cost += (ll)sz[u] * (ll)(n - sz[u]);
  43. 		return cost;
  44. 	}
  45.  
  46. 	void child_cost_dfs(int u,int par){
  47. 		for (int v : vec[u])
  48. 		  if (v != par){
  49. 		  	child_cost_dfs(v,u);
  50. 		  	child_cost[u] += child_cost[v] + sz[v];
  51. 		  }
  52. 	}
  53.  
  54. 	void reroot_dfs(int u,int par,ll cur){
  55. 		R[u] = child_cost[u] + cur;
  56. 		maxi(maxR,R[u]);
  57.  
  58. 		for (int v : vec[u])
  59. 			if (v != par) cur += child_cost[v] + sz[v];
  60.  
  61. 		for (int v : vec[u])
  62. 		    if (v != par)
  63. 		      reroot_dfs(v,u,cur - child_cost[v] - sz[v] + sz[1] - sz[v]);
  64. 	}
  65.  
  66. 	void perform_reroot(int n){
  67. 		//->R : reroot
  68. 		child_cost_dfs(1,0);
  69. 		reroot_dfs(1,0,0);
  70. 	}
  71.  
  72. 	void middle_dfs(int u,int par,ll S,int n,int n1,int n3,ll R1,ll R3){
  73. 		for (int v : vec[u])
  74. 		  if (v != par)
  75. 		     middle_dfs(v,u,S,n,n1,n3,R1,R3);
  76.  
  77. 		V[u][0] = (ll)D[u] * S + R[u] * (ll)n1;
  78. 		V[u][1] = (ll)D[u] * S + R[u] * (ll)n3; 
  79.  
  80. 		ll &f = dp[u];
  81. 		f = V[u][0] + V[u][1];
  82.  
  83. 		for (int v : vec[u])if (v != par){
  84. 			maxi(f,V[u][0] + V[v][1]);
  85. 			maxi(f,V[u][1] + V[v][0]);
  86.  
  87. 			maxi(V[u][0],V[v][0]);
  88. 			maxi(V[u][1],V[v][1]);
  89. 		}
  90.  
  91. 		f -= 2*(ll)D[u] * S;
  92.  
  93. 		f += (ll)(n + n1) * (ll)n3 + (ll)(n + n3) * (ll)n1;
  94. 		f += R3 * (ll)(n + n1);
  95. 		f += R1 * (ll)(n + n3);
  96. 	}
  97.  
  98. 	ll middle_cost(int n,int n1,int n3,ll R1,ll R3){
  99.  
  100. 		ll S = (ll)n1 * (ll)n3;
  101.  
  102. 		middle_dfs(1,0,S,n,n1,n3,R1,R3);
  103. 		ll cost = 0;
  104.  
  105. 		for (int u = 1 ; u <= n ; u++)
  106. 		  maxi(cost,dp[u]);
  107.  
  108. 	    return cost;
  109. 	}
  110. } tree[3];
  111. int n[3];
  112.  
  113. void input_tree(){
  114. 	for (int i = 0 ; i < 3 ; i++){
  115. 		cin >> n[i];
  116. 		for (int m = 1 ; m < n[i] ; m++){
  117. 			int u,v;
  118. 			cin >> u >> v;
  119. 			tree[i].add_edge(u,v);
  120. 		}
  121. 	}
  122. }
  123.  
  124. ll solve(){
  125. 	ll res = 0;
  126. 	int N = 3;
  127.  
  128. 	for (int id = 0 ; id < N ; id++){
  129. 		tree[id].init_dfs(1,0);
  130. 		res += tree[id].calc_self_cost(n[id]);
  131. 	}
  132.  
  133. 	for (int id = 0 ; id < N ; id++)
  134. 	  tree[id].perform_reroot(n[id]);
  135.  
  136. 	ll tmp = 0;
  137. 	for (int id = 0 ; id < N ; id++){
  138.  
  139. 		int i1 = (id + 1) % N,i2 = (id + 2) % N;
  140. 		ll R1 = tree[i1].maxR,R2 = tree[i2].maxR;
  141.  
  142. 		tmp = max(tmp,tree[id].middle_cost(n[id],n[i1],n[i2],R1,R2)); //??additional cost)
  143. 	}
  144.  
  145. 	res += tmp;
  146. 	return res;
  147. }
  148.  
  149. int main(){
  150. 	ios_base::sync_with_stdio(false);
  151. 	cin.tie(0);cout.tie(0);
  152.  
  153. 	freopen("3cay.inp","r",stdin);
  154. 	freopen("3cay.ans","w",stdout);
  155.  
  156. 	int stt;cin >> stt;
  157.  
  158. 	input_tree();
  159.  
  160. 	cout << solve();
  161.  
  162. 	return 0;
  163. }
  164.  
Success #stdin #stdout 0.01s 34176KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pWAcAZ
language:
C++14 (gcc 8.3)
created:
4 days 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!