Background

Windingly passing through others’ lips and teeth.

How many days and nights have I heard your story.

Could it be that this one word, “love,”

Cannot be understood even if one throws away life and death.

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.

Who goes from life to death, who worries about gain and loss,

There is not much time left even to look at each other.

The person in the painting secretly—his heart sways and his spirit is lost.

A drop of tears blurs the whole page.

Waving ink to draw eyebrows and eyes, lifting the brush to trace the hair at the temples.

With just a few strokes, it turns out to be like this.

At midnight where no one is, unrolling the scroll to the moon,

Suddenly I understand this longing.

Whose signature wrote the name.

———— “Heartfelt Autumn”

Background

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?

Problem 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

Test ID	N	M	Special Properties
$1$	$100$	$100$	None
$2$
$3$		$1000$
$4$	$10000$
$5$			$1$
$6$			$1,2$
$7$
$8$	$30000$	$100000$	None
$9$
$10$		$300000$

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