TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

89.7% (514/573)

Tags

Description

現在給定一個 N 個節點的樹,由 N1 條邊連接,第 i 條邊連接點 uivi,且邊上有一顆種類 ki 的堅果。

請回答 Q 筆詢問,每次詢問會給定 si,ti,現在考慮從 si 出發、用最短路徑走到 ti 的路徑,並收集所有路徑上的堅果。假設對於種類 x 的堅果我們收集到了 Cx 個,請問有多少堅果種類對 (a,b),滿足 Ca>0,Cb>0,Ca×2=Cb?注意到每筆詢問是獨立的,每次詢問收集完後會再將堅果放回去。

Input Format

輸入第一行有兩個正整數 N,Q,分別代表樹的大小與詢問的數量。

接下來 N1 行每行有三個正整數 ui,vi,ki,代表有一條從 uivi 的無向邊,這條邊上面有一顆種類 ki 的堅果。

接下來 Q 行每行有兩個正整數 si,ti,代表詢問的兩個參數。

  • 1N,Q105
  • 1ui,vi,si,tiN
  • 1ki105

Output Format

輸出 Q 行,第 i 行上有一個整數代表第 i 筆詢問的答案。

Sample Input 1

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

Sample Output 1

0
0
0
2
1
2
2

Hints

Problem Source

IOICamp 2020 Day2 pG

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~50 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 262144 65536 1 2
1 5000 262144 65536 2
2 5000 262144 65536 2
3 5000 262144 65536 2
4 5000 262144 65536 2
5 5000 262144 65536 2
6 5000 262144 65536 2
7 5000 262144 65536 2
8 5000 262144 65536 2
9 5000 262144 65536 2
10 5000 262144 65536 2
11 5000 262144 65536 2
12 5000 262144 65536 2
13 5000 262144 65536 2
14 5000 262144 65536 2
15 5000 262144 65536 2
16 5000 262144 65536 2
17 5000 262144 65536 2
18 5000 262144 65536 2
19 5000 262144 65536 2
20 5000 262144 65536 2
21 5000 262144 65536 2
22 5000 262144 65536 2
23 5000 262144 65536 2
24 5000 262144 65536 2
25 5000 262144 65536 2
26 5000 262144 65536 2
27 5000 262144 65536 2
28 5000 262144 65536 2
29 5000 262144 65536 2
30 5000 262144 65536 2
31 5000 262144 65536 2
32 5000 262144 65536 2
33 5000 262144 65536 2
34 5000 262144 65536 2
35 5000 262144 65536 2
36 5000 262144 65536 2
37 5000 262144 65536 2
38 5000 262144 65536 2
39 5000 262144 65536 2
40 5000 262144 65536 2
41 5000 262144 65536 2
42 5000 262144 65536 2
43 5000 262144 65536 2
44 5000 262144 65536 2
45 5000 262144 65536 2
46 5000 262144 65536 2
47 5000 262144 65536 2
48 5000 262144 65536 2
49 5000 262144 65536 2
50 5000 262144 65536 2