Description

In the first month of the first year of Jingning (33 BC), the night before Zhaojun left for the frontier.

The painter stumbled and crashed as he came to the palace where Zhaojun lived.

I heard that city in the northern land
Is covered by winter snow all day long
By the time old friends part forever and walk farther and farther away
In the blink of an eye, it is already two lifetimes apart
—— “Heartfelt Autumn”

If they could never meet again, the painter thought, he wanted to leave something for Zhaojun.

He wanted to give his paintbrush to Zhaojun.

There are $N$ rooms in Zhaojun’s palace, connected by $N-1$ roads.

The painter is now in the entrance hall room $S$. He vaguely remembers that Zhaojun’s room is number $T$.

Outside the window, the wind and rain rage. Inside the palace it flickers between light and dark, and there is not a single shadow of a person.

The painter walks into the dim corridor. On the wall of each corridor, there are several maple leaves painted—these were painted earlier at Zhaojun’s request. Zhaojun said she especially liked autumn, and especially the maple leaves of autumn.

How many past events did we talk about side by side—before we knew it, dusk had arrived.
—— “Heartfelt Autumn”

The corridor is extremely dark. The painter wants to light the candles prepared inside. He remembers Zhaojun had a habit: in each corridor, the number of candles equals the number of maple leaves on the wall. If Zhaojun wants to light the candles in a corridor, she will light them all. At that moment, Zhaojun considers that corridor to be lit up, and she will not light up any corridor whose number of maple leaves is less than that corridor’s.

This should be the last time coming to this place, the painter thought. He wants to follow Zhaojun’s habit and walk to Zhaojun’s room. At the same time, the painter does not want to go back the way he came, so he will not take any corridor he has already walked through.

Now the painter wants to know: when he walks from the palace hall $S$ to Zhaojun’s room $T$, without going back, what is the maximum number of corridors he can light up?

Input Format

The first line contains an integer $N$, meaning the number of rooms in the palace.

Next there are $N-1$ lines. Each line contains three integers $u_{i}, v_{i}, leaf_{i}$, meaning there is a corridor between $u$ and $v$, and there are $leaf_{i}$ maple leaves painted in that corridor.

Next is an integer $M$.

The last $M$ lines each contain two integers $S_{i}, T_{i}$.

Output Format

Output $M$ lines. For each query $S_{i}, T_{i}$, output the maximum number of corridors that can be lit.

5
1 2 5
2 3 1
1 4 1
3 5 4
3
2 1
4 2
1 1

1
2
0

7
1 2 1
1 3 5
2 4 1
4 5 4
5 6 1
1 7 1
5
7 5
7 6
2 7
1 1
2 4

4
4
2
0
1

20
1 2 1
1 3 3
2 4 5
1 5 1
5 6 5
1 7 5
1 8 4
7 9 1
8 10 2
1 11 1
2 12 5
3 13 1
3 14 3
3 15 3
10 16 1
5 17 1
12 18 5
7 19 4
7 20 5
10
10 3
17 16
11 9
4 6
16 17
11 16
11 11
13 11
2 1
10 11

2
3
2
3
3
2
0
2
1
2

Hint

Constraints

Special property $1$: $1<=leaf_{i}<=2$.

Special property $2$: $u_{i}+1=v_{i}$.

For all testdata, it is guaranteed that $1<=leaf_{i}<=5$.

Analysis of Sample 1:

Query $1$: From $2$ to $1$, at most $1$ corridor can be lit ($2-1$).

Query $2$: From $4$ to $2$, at most $2$ corridors can be lit ($4-1, 1-2$).

Query $3$: Obviously, no corridor can be lit.

Analysis of Sample 2:

)

Query $1$: From $7$ to $5$, $4$ corridors can be lit ($7-1, 1-2, 2-4, 4-5$).

Query $2$: From $7$ to $6$, $4$ corridors can be lit ($7-1, 1-2, 2-4, 4-5$). Not lighting ($5-6$) is because after lighting ($4-5$), it is impossible to light a corridor whose number of maple leaves is less than $4$. It is easy to see this is optimal. Alternatively, do not light ($4-5$) and instead light ($5-6$); this is also optimal.

Query $3$: From $2$ to $7$, $2$ corridors can be lit ($2-1$, $1-7$).

Query $4$: Do not pass through any corridor.

Query $5$: Pass through $1$ corridor ($2-4$).

Where can sorrow be made whole. Autumn rests on the hearts of those who part. Even banana leaves, without rain, still rustle. All say the late-cool weather is good; there is a bright moon, yet one fears climbing the tower.

Let age and affairs end within dreams. Flowers fall empty, smoke and waters flow. The swallows have left to return, while the traveler still lingers. Drooping willows cannot hold back the skirt belt. Long is it, the rope that ties the moving boat.

Translated by ChatGPT 5