fork(8) download
copy 
  1. #include <bits/stdc++.h>
  2. #define sz(v) ((int)(v).size())
  3. using namespace std;
  4. const int MAXN = 250005;
  5. using lint = long long;
  6. using pi = pair<lint, int>;
  7.  
  8. int n, vis[MAXN];
  9. int csz[MAXN], msz[MAXN];
  10. vector<pi> gph[3][MAXN];
  11.  
  12. void dfsc(int x, int p, vector<int> &dfn){
  13. 	csz[x] = 1;
  14. 	msz[x] = 0;
  15. 	dfn.push_back(x);
  16. 	for(auto &i : gph[0][x]){
  17. 		if(i.second != p && !vis[i.second]){
  18. 			dfsc(i.second, x, dfn);
  19. 			csz[x] += csz[i.second];
  20. 			msz[x] = max(msz[x], csz[i.second]);
  21. 		}
  22. 	}
  23. }
  24.  
  25. int get_center(int x){
  26. 	vector<int> dfn;
  27. 	dfsc(x, -1, dfn);
  28. 	pi ret(1e9, 1e9);
  29. 	for(auto &i : dfn){
  30. 		int foo = max(msz[i], sz(dfn) - csz[i]);
  31. 		ret = min(ret, pi(foo, i));
  32. 	}
  33. 	return ret.second;
  34. }
  35.  
  36. struct edg{ int s, e; lint x; };
  37.  
  38. namespace tree{
  39. 	int lg[2*MAXN], din[MAXN], dout[MAXN], piv;
  40. 	int lev[MAXN];
  41. 	lint dep[MAXN];
  42. 	pi spt[19][MAXN * 2];
  43. 	void dfs(int x, int p){
  44. 		din[x] = ++piv;
  45. 		spt[0][din[x]] = pi(lev[p], p);
  46. 		for(auto &i : gph[1][x]){
  47. 			if(i.second != p){
  48. 				lev[i.second] = lev[x] + 1;
  49. 				dep[i.second] = dep[x] + i.first;
  50. 				dfs(i.second, x);
  51. 			}
  52. 		}
  53. 		dout[x] = ++piv;
  54. 		spt[0][dout[x]] = pi(lev[p], p);
  55. 	}
  56. 	void init(){
  57. 		dfs(1, 0);
  58. 		for(int i=1; i<=2*n; i++){
  59. 			lg[i] = lg[i-1];
  60. 			while((2 << lg[i]) <= i) lg[i]++;
  61. 		}
  62. 		for(int i=1; i<19; i++){
  63. 			for(int j=1; j<=2*n; j++){
  64. 				spt[i][j] = spt[i-1][j];
  65. 				if(j + (1<<(i-1)) <= 2*n) spt[i][j] = min(spt[i][j], spt[i-1][j + (1<<(i-1))]);
  66. 			}
  67. 		}
  68. 	}
  69. 	int lca(int x, int y){
  70. 		if(din[x] > din[y]) swap(x, y);
  71. 		if(dout[y] <= dout[x]) return x;
  72. 		// [dout[y], din[x]]
  73. 		int l = lg[din[y] - dout[x] + 1];
  74. 		return min(spt[l][dout[x]], spt[l][din[y] - (1<<l) + 1]).second;
  75. 	}
  76. 	vector<edg> compress(vector<int> &v){
  77. 		auto in = [&](int x, int y){
  78. 			return din[x] <= din[y] && dout[y] <= dout[x];
  79. 		};
  80. 		v.resize(unique(v.begin(), v.end()) - v.begin());
  81. 		vector<int> stk;
  82. 		vector<edg> dap;
  83. 		for(auto &i : v){
  84. 			while(sz(stk) && !in(stk.back(), i)) stk.pop_back();
  85. 			if(sz(stk)){
  86. 				dap.push_back({stk.back(), i, dep[i] - dep[stk.back()]});
  87. 			}
  88. 			stk.push_back(i);
  89. 		}
  90. 		return dap;
  91. 	}
  92. }
  93.  
  94. lint dap[MAXN];
  95. lint dp[MAXN], val[MAXN], pdp[MAXN];
  96.  
  97. void get_shortest_path(vector<pi> cnd, vector<int> dfn){
  98. 	for(auto &i : cnd) val[i.second] = dp[i.second] = i.first;
  99. 	reverse(dfn.begin(), dfn.end());
  100. 	for(auto &i : dfn){
  101. 		for(auto &j : gph[2][i]){
  102. 			dp[i] = min(dp[i], dp[j.second] + j.first);
  103. 		}
  104. 	}
  105. 	reverse(dfn.begin(), dfn.end());
  106. 	for(auto &i : dfn){
  107. 		if(sz(gph[2][i]) == 0) continue;
  108. 		lint curMin = min(pdp[i], val[i]);
  109. 		reverse(gph[2][i].begin(), gph[2][i].end());
  110. 		for(auto &j : gph[2][i]){
  111. 			pdp[j.second] = min(pdp[j.second], j.first + curMin);
  112. 			curMin = min(curMin, dp[j.second] + j.first);
  113. 		}
  114. 		curMin = min(pdp[i], val[i]);
  115. 		reverse(gph[2][i].begin(), gph[2][i].end());
  116. 		for(auto &j : gph[2][i]){
  117. 			pdp[j.second] = min(pdp[j.second], j.first + curMin);
  118. 			curMin = min(curMin, dp[j.second] + j.first);
  119. 		}
  120. 	}
  121. 	for(auto &i : cnd){
  122. 		lint ans = pdp[i.second];
  123. 		for(auto &j : gph[2][i.second]){
  124. 			ans = min(ans, dp[j.second] + j.first);
  125. 		}
  126. 		dap[i.second] = min(dap[i.second], i.first + ans);
  127. 	}
  128. }
  129.  
  130. void dfs(int x, int p, lint d, vector<pi> &dfn){
  131. 	dfn.emplace_back(d, x);
  132. 	for(auto &i : gph[0][x]){
  133. 		if(i.second != p && !vis[i.second]){
  134. 			dfs(i.second, x, d + i.first, dfn);
  135. 		}
  136. 	}
  137. }
  138.  
  139. vector<int> toComp[MAXN];
  140. vector<pi> dfn[MAXN];
  141.  
  142. pi cnt[MAXN * 40];
  143. int ptr[MAXN * 2];
  144.  
  145. void SORT(){
  146. 	memset(ptr, 0, sizeof(ptr));
  147. 	for(int i=1; i<=n; i++){
  148. 		for(auto &j : toComp[i]){
  149. 			ptr[tree::din[j]]++;
  150. 		}
  151. 	}
  152. 	for(int i=1; i<=n*2; i++){
  153. 		ptr[i] += ptr[i-1];
  154. 	}
  155. 	int sum = ptr[2*n];
  156. 	for(int i=1; i<=n; i++){
  157. 		for(auto &j : toComp[i]){
  158. 			cnt[--ptr[tree::din[j]]] = pi(i, j);
  159. 		}
  160. 		toComp[i].clear();
  161. 	}
  162. 	for(int i=0; i<sum; i++){
  163. 		toComp[cnt[i].first].push_back(cnt[i].second);
  164. 	}
  165. }
  166.  
  167. int main(){
  168. 	scanf("%d",&n);
  169. 	for(int i=0; i<2; i++){
  170. 		for(int j=1; j<n; j++){
  171. 			int s, e, x; scanf("%d %d %d",&s,&e,&x);
  172. 			gph[i][s].emplace_back(x, e);
  173. 			gph[i][e].emplace_back(x, s);
  174. 		}
  175. 	}
  176. 	tree::init();
  177. 	memset(dap, 0x3f, sizeof(dap));
  178. 	memset(dp , 0x3f, sizeof(dp ));
  179. 	memset(pdp, 0x3f, sizeof(pdp));
  180. 	memset(val, 0x3f, sizeof(val));
  181. 	queue<int> que;
  182. 	que.push(1);
  183. 	while(!que.empty()){
  184. 		int x = que.front(); que.pop();
  185. 		x = get_center(x);
  186. 		vis[x] = 1;
  187. 		dfs(x, 0, 0, dfn[x]);
  188. 		if(sz(dfn[x]) == 1) continue;
  189. 		for(auto &i : dfn[x]){
  190. 			toComp[x].push_back(i.second);
  191. 		}
  192. 		for(auto &i : gph[0][x]){
  193. 			if(!vis[i.second]){
  194. 				que.push(i.second);
  195. 			}
  196. 		}
  197. 	}
  198. 	SORT();
  199. 	for(int i=1; i<=n; i++){
  200. 		int foo = sz(toComp[i]);
  201. 		for(int j=1; j<foo; j++){
  202. 			int bar = tree::lca(toComp[i][j-1], toComp[i][j]);
  203. 			toComp[i].push_back(bar);
  204. 		}
  205. 	}
  206. 	SORT();
  207. 	for(int i=1; i<=n; i++){
  208. 		if(sz(toComp[i]) == 0) continue;
  209. 		auto edgList = tree::compress(toComp[i]);
  210. 		for(auto &i : edgList){
  211. 			gph[2][i.s].emplace_back(i.x, i.e);
  212. 		}
  213. 		get_shortest_path(dfn[i], toComp[i]);
  214. 		for(auto &i : toComp[i]){
  215. 			gph[2][i].clear();
  216. 			dp[i] = pdp[i] = val[i] = 1e18;
  217. 		}
  218. 	}
  219. 	for(int i=1; i<=n; i++) printf("%lld\n", dap[i]);
  220. }
  221.  
  222.  
  223.  
Success #stdin #stdout 0.02s 42644KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hTAcla
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!