{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003e这个问题的原始标题是“没有一个点的树积度Voronoi图查询”。\u003c/span\u003e\u003c/p\u003e\u003cp\u003e给定两个大小为$$$N$$$的带权树$$$T_1,\\ T_2$$$,其中每个顶点都标有数字$$$1 \\ldots N$$$。设$$$dist(T_1,\\ i,\\ j)$$$为树$$$T_1$$$中从节点$$$i$$$到$$$j$$$的最短路径的总权重,并类似地定义$$$dist(T_2,\\ i,\\ j)$$$。\u003c/p\u003e\u003cp\u003e考虑一个大小为$$$N$$$的点集。类似于曼哈顿度量(实际上,这是它的一般化),我们可以定义两点$$$1 \\le i,\\ j \\le N$$$之间的距离:它是两个距离$$$dist(T_1,\\ i,\\ j) + dist(T_2,\\ i,\\ j)$$$的和。对于每个$$$1 \\le i \\le N$$$,请确定从点$$$i$$$到点的“最近点”。形式上,对于每个$$$i$$$,你应该找到$$$min_{j \\neq i}{dist(T_1,\\ i,\\ j) + dist(T_2,\\ i,\\ j)}$$$。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行给出一个整数$$$N$$$,表示两棵树中顶点的数量($$$2 \\le N \\le 250\\,000$$$)。\u003c/p\u003e\u003cp\u003e在接下来的$$$N-1$$$行中,给出第一棵树的描述。每个$$$N-1$$$行包含三个整数$$$S_i, E_i, W_i$$$,表示连接两个顶点$$$S_i, E_i$$$的边的权重为$$$W_i$$$($$$1 \\le S_i, E_i \\le N, 1 \\le W_i \\le 10^9$$$)。\u003c/p\u003e\u003cp\u003e在接下来的$$$N-1$$$行中,以相同的格式给出第二棵树的描述。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e打印$$$N$$$行,每行包含一个整数。在第$$$i$$$行,你应该打印一个整数,表示点$$$i$$$的答案。\u003c/p\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n1 2 10\n2 4 20\n3 4 30\n4 5 50\n1 2 15\n1 3 25\n1 4 35\n1 5 25\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e25\n25\n85\n65\n105\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e9\n5 7 6577\n4 5 8869\n5 9 9088\n2 1 124\n6 2 410\n2 8 8154\n4 8 4810\n3 4 4268\n3 9 763\n6 2 8959\n7 4 7984\n3 8 504\n8 6 9085\n5 2 4861\n1 9 8539\n1 7 7834\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e18084\n9369\n9582\n23430\n26694\n9369\n23430\n9582\n22988\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}