Problem Description

There is an undirected tree with $ N $ vertices, numbered from $ 1 $ to $ N $, and $ N-1 $ edges, numbered from $ 1 $ to $ N-1 $. Edge $ i $ connects vertex $ A_i $ and vertex $ B_i $ and has a weight of $ C_i $. Note that the weight values can be negative.

A connected subgraph of this tree is called a "driving subtree", and specifically one that includes vertex $ u $ and vertex $ v $ is called a "u-v driving subtree". The sum of the weights of the edges in a driving subtree is called the "fun" of that driving subtree.

Given $ Q $ pairs of integers $ (U_i, V_i) $, answer the following question for each $ i $:

• What is the maximum possible fun of the u-v driving subtree?

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $ B_1 $ $ C_1 $ : $ A_{N-1} $ $ B_{N-1} $ $ C_{N-1} $ $ Q $ $ U_1 $ $ V_1 $ : $ U_Q $ $ V_Q $

Output Format

Output $ Q $ lines. The $ i $-th line should contain the maximum possible fun of the u-v driving subtree.

Sample Input and Output

Sample Input #1

7
1 3 -10
2 3 20
3 4 -1
1 6 1
5 6 3
6 7 2
3
3 4
5 7
2 6

Sample Output #1

19
16
16

Sample Input #2

7
1 3 -1100000
2 3 -1010000
3 4 -1001000
1 6 -1000100
5 6 -1000010
6 7 -1000001
3
3 4
5 7
2 6

Sample Output #2

-1001000
-2000011
-3110100

Sample Input #3

18
2 8 -133775141
3 16 -311103251
4 11 849496136
9 14 -442278959
8 13 946094213
8 14 714669159
5 8 210787603
5 11 8973730
10 15 581490293
10 16 -347827761
10 11 -126622449
7 11 431568122
6 7 -458490133
6 17 -314331217
1 6 -220056853
1 12 -981864951
12 18 183014767
20
1 15
7 10
6 12
1 18
3 16
4 8
9 12
2 14
1 11
3 8
14 17
4 17
12 18
3 17
1 10
5 9
9 15
4 13
5 11
4 7

Sample Output #3

2937909821
3616456807
2139059637
2139059637
2957525795
3616456807
1696780678
3482681666
2937909821
2957525795
2843635457
2843635457
2139059637
2184704445
2937909821
3174177848
3174177848
3616456807
3616456807
3616456807

Notes/Hints

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i < B_i \leq N \ (1 \leq i \leq N - 1)$
• The given graph forms a tree
• $-10^9 \leq C_i \leq 10^9 \ (1 \leq i \leq N - 1)$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq U_i < V_i \leq N \ (1 \leq i \leq Q)$
• All input values are integers

见题面 Input 部分

见题面 Output 部分