fork(4) download
  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
stdin
Standard input is empty
stdout
Standard output is empty