245 . 收集堅果

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

89.7% (514/573)

Tags

ioicamp ioicamp-2020

Description

現在給定一個 $N$ 個節點的樹，由 $N - 1$ 條邊連接，第 $i$ 條邊連接點 $u_i$ 與 $v_i$，且邊上有一顆種類 $k_i$ 的堅果。

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

Input Format

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

接下來 $N - 1$ 行每行有三個正整數 $u_i, v_i, k_i$，代表有一條從 $u_i$ 到 $v_i$ 的無向邊，這條邊上面有一顆種類 $k_i$ 的堅果。

接下來 $Q$ 行每行有兩個正整數 $s_i, t_i$，代表詢問的兩個參數。

  • $1 \leq N, Q \leq 10^ 5$
  • $1 \leq u_i, v_i, s_i, t_i \leq N$
  • $1 \leq k_i \leq 10^ 5$

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
Submit
Back to Top