{"problem":{"name":"Through Path","description":{"content":"We have a tree with $N$ vertices and $N-1$ edges, where the vertices are numbered $1, 2, \\dots, N$ and the edges are numbered $1, 2, \\dots, N-1$. Edge $i$ connects Vertices $a_i$ and $b_i$.   Each ver","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc187_e"},"statements":[{"statement_type":"Markdown","content":"We have a tree with $N$ vertices and $N-1$ edges, where the vertices are numbered $1, 2, \\dots, N$ and the edges are numbered $1, 2, \\dots, N-1$. Edge $i$ connects Vertices $a_i$ and $b_i$.  \nEach vertex in the tree has an integer written on it. Let $c_i$ be the integer written on Vertex $i$. Initially, $c_i = 0$.\nYou will be given $Q$ queries. The $i$\\-th query, consisting of integers $t_i$, $e_i$, and $x_i$, is as follows:\n\n*   If $t_i = 1$: for each Vertex $v$ reachable from Vertex $a_{e_i}$ without visiting Vertex $b_{e_i}$ by traversing edges, replace $c_v$ with $c_v + x_i$.\n*   If $t_i = 2$: for each Vertex $v$ reachable from Vertex $b_{e_i}$ without visiting Vertex $a_{e_i}$ by traversing edges, replace $c_v$ with $c_v + x_i$.\n\nAfter processing all queries, print the integer written on each vertex.\n\n## Constraints\n\n*   All values in input are integers.\n*   $2 \\le N \\le 2 \\times 10^5$\n*   $1 \\le a_i, b_i \\le N$\n*   The given graph is a tree.\n*   $1 \\le Q \\le 2 \\times 10^5$\n*   $t_i \\in {1, 2}$\n*   $1 \\le e_i \\le N-1$\n*   $1 \\le x_i \\le 10^9$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$a_1$ $b_1$\n$\\vdots$\n$a_{N-1}$ $b_{N-1}$\n$Q$\n$t_1$ $e_1$ $x_1$\n$\\vdots$\n$t_Q$ $e_Q$ $x_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc187_e","tags":[],"sample_group":[["5\n1 2\n2 3\n2 4\n4 5\n4\n1 1 1\n1 4 10\n2 1 100\n2 2 1000","11\n110\n1110\n110\n100\n\nIn the first query, we add $1$ to each vertex reachable from Vertex $1$ without visiting Vertex $2$, that is, Vertex $1$.  \nIn the second query, we add $10$ to each vertex reachable from Vertex $4$ without visiting Vertex $5$, that is, Vertex $1, 2, 3, 4$.  \nIn the third query, we add $100$ to each vertex reachable from Vertex $2$ without visiting Vertex $1$, that is, Vertex $2, 3, 4, 5$.  \nIn the fourth query, we add $1000$ to each vertex reachable from Vertex $3$ without visiting Vertex $2$, that is, Vertex $3$."],["7\n2 1\n2 3\n4 2\n4 5\n6 1\n3 7\n7\n2 2 1\n1 3 2\n2 2 4\n1 6 8\n1 3 16\n2 4 32\n2 1 64","72\n8\n13\n26\n58\n72\n5"],["11\n2 1\n1 3\n3 4\n5 2\n1 6\n1 7\n5 8\n3 9\n3 10\n11 4\n10\n2 6 688\n1 10 856\n1 8 680\n1 8 182\n2 2 452\n2 4 183\n2 6 518\n1 3 612\n2 6 339\n2 3 206","1657\n1657\n2109\n1703\n1474\n1657\n3202\n1474\n1247\n2109\n2559"]],"created_at":"2026-03-03 11:01:14"}}