酸欠少女
小風手上拿著一棵具有 N 個節點的樹,這棵樹的節點以 1,2,…,N 表示。然而,標號為 1 的節點上有一株病毒,這個病毒會沿著樹上的邊擴散,為了盡可能保護這棵樹,小風想要切除樹上的一些邊,使得被感染的節點不超過 K 個,不過有些邊是沒辦法被切除的,請幫小風計算至少要切除幾條邊才能夠達成目標?
輸入第一行包含兩個正整數 N,K(1≤K≤N≤5×105)。 接下來 N−1 行每一行都有三個整數 a,b,c(1≤a,b≤n,c∈0,1),代表著樹上的一條邊 (a,b),若 c=1 代表這條邊可以被切除,否則該條邊不能被切除,輸入保證會形成一棵樹。
請輸出一個整數代表至少要移除多少條邊才能讓被感染的節點不超過 K 個,如果無法達成,請輸出 −1。
CSAcademy