問題文

NN 頂点の木が与えられます。 i=1,2,,N1i = 1, 2, \dots, N-1 について ii 番目の辺は頂点 uiu_i と 頂点 viv_i を結んでいます。

また、長さ N1N-1 の正整数列 A,BA, B が与えられます。

次のような NN 頂点の有向グラフ GG を考えます。

  • i=1,2,,N1i = 1, 2, \dots, N-1 について、頂点 uiu_i から頂点 viv_i に重み AiA_i の辺を張る
  • i=1,2,,N1i = 1, 2, \dots, N-1 について、頂点 viv_i から頂点 uiu_i に重み BiB_i の辺を張る

v=1,2,,Nv = 1, 2, \dots, N について、頂点 vv を根とする最小有向全域木の重みを求めてください。

制約

  • 2N2×1052 \leq N \leq 2 \times 10^5
  • 1ui,viN (i=1,2,,N1)1 \leq u_i, v_i \leq N \ (i = 1, 2, \dots, N-1)
  • 1Ai,Bi109 (i=1,2,,N1)1 \leq A_i, B_i \leq 10^9 \ ( i = 1, 2, \dots, N-1)
  • 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられます。

NN
u1u_1 v1v_1 A1A_1 B1B_1
u2u_2 v2v_2 A2A_2 B2B_2
\vdots
uN1u_{N-1} vN1v_{N-1} AN1A_{N-1} BN1B_{N-1}

出力

v=1,2,,Nv = 1, 2, \dots, N について、頂点 vv を根とする最小有向全域木の重みを空白区切りで出力してください。

入力例
3
1 2 5 7
1 3 4 8
出力例
9 11 13

例えば、頂点 11 を根とする最小有向全域木の重みは 5+4=95 + 4 = 9 です。

出力する値が 32bit 整数型に収まらないことがあることに注意してください。

提出


Go (1.21)