756 . 病毒

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (3/3)

Tags

apcsc apcsc-graph

Description

小風手上拿著一棵具有 $N$ 個節點的樹，這棵樹的節點以 $1, 2, \ldots, N$ 表示。然而，標號為 $1$ 的節點上有一株病毒，這個病毒會沿著樹上的邊擴散，為了盡可能保護這棵樹，小風想要切除樹上的一些邊，使得被感染的節點不超過 $K$ 個，不過有些邊是沒辦法被切除的，請幫小風計算至少要切除幾條邊才能夠達成目標？

Input Format

輸入第一行包含兩個正整數 $N, K (1 \leq K \leq N \leq 5 \times 10^ 5)$。
接下來 $N - 1$ 行每一行都有三個整數 $a, b, c (1 \leq a, b \leq n, c \in {0, 1})$，代表著樹上的一條邊 $(a, b)$，若 $c = 1$ 代表這條邊可以被切除，否則該條邊不能被切除，輸入保證會形成一棵樹。

Output Format

請輸出一個整數代表至少要移除多少條邊才能讓被感染的節點不超過 $K$ 個，如果無法達成，請輸出 $-1$。

Sample Input 1

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

Sample Output 1

1

Sample Input 2

10 7
1 3 1
3 5 1
1 9 1
3 8 1
6 7 1
10 1 0
8 2 0
4 5 1
6 1 0

Sample Output 2

1

Sample Input 3

3 2
3 2 0
3 1 0

Sample Output 3

-1

Hints

Problem Source

CSAcademy

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 65536 1 2
1 3000 524288 65536 1 2
2 3000 524288 65536 1 2
3 3000 524288 65536 2
4 3000 524288 65536 2
5 3000 524288 65536 2
6 3000 524288 65536 2
7 3000 524288 65536 2
8 3000 524288 65536 2
9 3000 524288 65536 2
10 3000 524288 65536 2
11 3000 524288 65536 2
12 3000 524288 65536 2
13 3000 524288 65536 2
14 3000 524288 65536 2
15 3000 524288 65536 2
16 3000 524288 65536 2
17 3000 524288 65536 2
18 3000 524288 65536 2
19 3000 524288 65536 2
20 3000 524288 65536 2
21 3000 524288 65536 2
22 3000 524288 65536 2
23 3000 524288 65536 2
24 3000 524288 65536 2
25 3000 524288 65536 2
26 3000 524288 65536 2
27 3000 524288 65536 2
28 3000 524288 65536 2
29 3000 524288 65536 2
30 3000 524288 65536 2
31 3000 524288 65536 2
32 3000 524288 65536 2
33 3000 524288 65536 2
34 3000 524288 65536 2
Submit
Back to Top