1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 #include #define FOR(i, a, b) for (int i=(a); i<(b); i++) #define PPC(x) __builtin_popcount((x)) #define ALL(x) (x).begin(), (x).end() #define pb push_back #define st first #define nd second using namespace std; const int maxN = 26000, mod = 1000000007; inline void addMod(long long& a, long long b) { a = (a + b) % mod; } inline void multMod(long long& a, long long b) { a = a * b % mod; } long long qpow(long long a, long long b) { long long res0 = 1; for (; b!=0; b>>=1) { if (b & 1) multMod(res0, a); multMod(a, a); } return res0; } vector > G[maxN]; vector pat; vector > T; //vector T[10000000]; int root; vector inds[2]; int cnt[maxN]; void dfs(int v, int fat) { if (root < v) T.pb(pat); for (auto p : G[v]) { short u, c; tie(u, c) = p; if (u != fat) { pat.pb(c); dfs(u, v); pat.pop_back(); } } } int main() { int n, k; scanf ("%d%d", &n, &k); FOR(i, 1, n) { int a, b, c; scanf ("%d%d%d", &a, &b, &c); G[a].pb({b, c}); G[b].pb({a, c}); } FOR(i, 1, n+1) dfs(root = i, 0); inds[0].resize(T.size()); iota(ALL(inds[0]), 0); FOR(i, 0, T.size()) { sort(ALL(T[i]), greater ()); T[i].pb(0); } FOR(d, 0, n-1) { vector &curr = inds[d&1], &nxt = inds[(d&1) ^ 1]; nxt.resize(0); for (int i : curr) cnt[T[i][d]]++; int ile = 0; short dig; FOR(c, 0, n+1) { if (ile + cnt[c] >= k) { dig = c; k -= ile; break; } ile += cnt[c]; } for (int i : curr) { if (T[i][d] == dig) nxt.pb(i); cnt[T[i][d]] = 0; } if (dig == 0) { inds[(n-1)&1] = nxt; break; } } int j = inds[(n-1)&1][0]; vector & t = T[j]; t.pop_back(); long long res = 0; for (short e : t) addMod(res, qpow(n, e)); printf("%lld\n", res); return 0; }