# Partial Sum on Tree
## Problem Statement
You are given a tree with $N$ nodes, labeled from $1$ to $N$. Initially, the value associated with each node is $0$. You need to process $Q$ queries. Each query consists of three integers $x, y, z$, meaning you should add the value $z$ to all nodes that lie on the unique shortest path between node $x$ and node $y$.
After performing all $Q$ queries, your task is to print the final value of each node, from node $1$ to node $N$.
## Input Format
The first line contains an integer $T$ ($1 \le T \le 10^4$) - the number of test cases.
For each test case:
- The first line contains a single integer $N$ ($1 \le N \le 10^5$) - the number of nodes in the tree.
- The next $N-1$ lines each contain two space-separated integers $u, v$ ($1 \le u, v \le N$, $u \ne v$), denoting an undirected edge between node $u$ and node $v$.
- The next line contains a single integer $Q$ ($1 \le Q \le 10^5$) - the number of queries.
- The next $Q$ lines each contain three space-separated integers $x, y, z$ ($1 \le x, y \le N$, $-10^6 \le z \le 10^6$), representing a query to add $z$ to all nodes on the path between $x$ and $y$.
## Output Format
For each test case, print $N$ space-separated integers on a new line. The $i$-th integer should be the final value of node $i$ after all queries have been processed.
## Sample Test Cases
### Sample Input 1
```
2
5
5 4
2 1
3 2
4 2
10
2 5 -8
5 2 -3
4 4 -6
4 3 -1
2 2 3
1 3 6
2 4 -8
4 4 -5
5 3 8
2 1 6
16
13 7
10 6
6 4
8 4
9 4
16 12
14 8
2 1
3 1
12 1
15 10
4 3
11 3
5 2
7 2
36
1 9 32344
16 8 335632
7 14 -184549
4 14 -566786
11 9 -710223
7 4 -902974
12 6 434571
13 14 471558
3 10 642273
3 7 292965
15 4 -643712
15 12 879886
15 8 -307835
15 5 -244965
10 8 612065
11 11 348816
3 6 527481
16 14 567975
12 7 -950446
14 5 -144486
6 7 -283238
6 1 353436
7 4 -748946
11 14 120982
1 12 -923018
13 9 -136443
2 15 564490
6 2 429536
8 7 -384482
1 13 -438491
7 8 -682297
4 2 570947
10 8 724338
4 10 906307
10 10 -968424
2 1 252342
```
### Sample Output 1
```
12 3 13 -23 -3
-838653 -2519479 1801473 2232885 -389451 4594633 -3947343 562115 -814322 2164423 -240425 344600 -103376 264694 247864 903607
```
## Constraints
- $1 \le T \le 10^4$
- $1 \le N \le 10^5$
- $1 \le Q \le 10^5$
- $1 \le u, v \le N$, $u \ne v$
- $1 \le x, y \le N$
- $-10^6 \le z \le 10^6$
- The sum of $N$ over all test cases does not exceed $2 \cdot 10^6$.
- The sum of $Q$ over all test cases does not exceed $2 \cdot 10^6$.
- Time Limit: 5 seconds
- Memory Limit: 256 MB
## Explanation
This problem requires efficiently handling path updates on a tree. For each query $(x, y, z)$, we need to identify all nodes on the unique shortest path between $x$ and $y$ and increment their values by $z$. Since initial node values are $0$, the final value of a node is the sum of all $z$ values from queries whose paths included that node. A common approach involves tree algorithms like Lowest Common Ancestor (LCA) combined with difference arrays or Heavy-Light Decomposition (HLD) to process path updates and retrieve final node values efficiently.
Loading problem statement...