a149. pE 紅黑邊樹 - 旦旦解題農場

內容

給定一棵樹，其中樹邊分成兩種顏色:黑色或紅色。現在定義一個序列$[a_1,a_2,...,a_k]$是"好的"如果它滿足以下條件:

- 如果你從$a_1$走最短路徑到$a_2$再走最短路徑到$a_3...$一直下去最後走到$a_k$，如果路徑上有經過任何一條"黑邊"，則稱這個序列是好的序列。

舉例來說:

這張圖中$[1,4,7],[5,5,3],[2,3,7]$等都是好的序列，而$[1,4,6],[5,5,5],[3,7,3]$就不是好的序列。

現在給你一張圖與一個數字$k$，求有多少種不同長度為$k$的好的序列。(若不考慮序列是否是好的，一共有$n^k$個相異的序列)

輸入說明

輸入第一行包含兩個正整數$n,k$，分別代表樹的大小與點序列長度。

接下來$n-1$行每行三個整數$a_i,b_i,c_i$代表$a_i$與$b_i$之間有一條邊，且若$c_i=0$代表此條邊為紅色，反之若$c_i=1$代表為黑色。

40%測資符合$n\le 1000,k=2$

100%測資符合$2\le n\le 10^5,2\le k\le 100,1\le a_i,b_i\le n,c_i\in \{0,1\}$

輸出說明

輸出"好的序列"的數量取$10^9+7$的餘數。

範例輸入

範例輸出

範例測資1:
252

範例測資2:
0

範例測資3:
210

測資資訊：

記憶體限制： 64 MB
不公開測資點#0 (5%): 1.0s , <1K
不公開測資點#1 (5%): 1.0s , <1K
不公開測資點#2 (5%): 1.0s , <1K
不公開測資點#3 (5%): 1.0s , <1K
不公開測資點#4 (5%): 1.0s , <1K
不公開測資點#5 (5%): 1.0s , <1K
不公開測資點#6 (5%): 1.0s , <1K
不公開測資點#7 (5%): 1.0s , <1M
不公開測資點#8 (5%): 1.0s , <10M
不公開測資點#9 (5%): 1.0s , <10M
不公開測資點#10 (5%): 1.0s , <10M
不公開測資點#11 (5%): 1.0s , <10M
不公開測資點#12 (5%): 1.0s , <10M
不公開測資點#13 (5%): 1.0s , <10M
不公開測資點#14 (5%): 1.0s , <10M
不公開測資點#15 (5%): 1.0s , <10M
不公開測資點#16 (5%): 1.0s , <10M
不公開測資點#17 (5%): 1.0s , <10M
不公開測資點#18 (5%): 1.0s , <10M
不公開測資點#19 (5%): 1.0s , <10M

提示：

由於這題很容易讓假解拿高分，因此將採用手動配分：

1. 若該題AC(所有測資點全對)則能拿到100%分數。

2. 若測資點0~7全對則能拿到40%分數，反之若有任一筆錯則0分。

標籤:

出處:

電神盃程式設計競賽 [管理者：

giver (垃圾)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」