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 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 //Marcin Knapik, Potyczki Algorytmiczne, Dzień 4. Zadanie "Szproty i Szczupaki"[B] // złożoność O(n log n log n) #include using namespace std; #define int ll #define vi vector #define f first #define s second #define pb push_back #define sz(s) (int)s.size() #define all(s) s.begin(), s.end() #define FOR(i, s) for(int i = 0; i < s; i++) #define ll long long #define pll pair #define vll vector #define pii pair #define vvl vector int n, k; const int N = 25004; #define vvi vector< vector > vvi mac(N); const int mod = 1e9+7; bitsettab[N]; int val; int ile[N]; ll fast(ll a, ll b){ ll ret = 1; ll pom = a; while(b){ if(b&1) ret = ((ll)ret*pom)%mod; pom = ((ll)pom*pom)%mod; b>>=1; } return ret; } vector > > G(N); vector > dfs(int start, int przodek = -1){ vector< pair< int, vector > > > syny; // nr, ile for(auto&u: G[start]) if(u.f != przodek) syny.pb({u.s, dfs(u.f, start)}); for(int i = 0; i < sz(syny); i++){ for(auto&u: syny[i].s){ for(int j = i+1; j < sz(syny); j++){ for(auto&v:syny[j].s){ int a = u.f, b = v.f; if(a < b) swap(a, b); mac[a][b] = u.s + v.s + (syny[i].f == val) + (syny[j].f == val); } } } } vector > ret; ret.pb({start, 0}); for(auto&u:syny){ for(auto&v:u.s){ int a = start, b = v.f; if(a < b) swap(a, b); mac[a][b] = v.s + (u.f == val); if((u.f == val)) v.s++; ret.pb({v.f, v.s}); } } return ret; } void oznacz(int x){ for(int i = 0 ; i< n; i++) for(int j = 0; j < i; j++) if(mac[i][j] != x) tab[i][j] = 0; } signed main(){ cin >> n >> k; for(int i = 0 ; i > a >> b >> c; a--, b--; G[a].pb({b, c}); G[b].pb({a, c}); maxi_koszt = max(maxi_koszt, c); } for(int i = 0; i < n; i++) mac[i].resize(i); ll ans = 0; for(int KK = maxi_koszt;KK >= 1; KK--){ val = KK; dfs(1); // for(int i = 0; i< n; i++){ // cout << i << "; "; // for(int j = 0; j < i; j++){ // cout << mac[i][j] << ' '; // } // cout << endl; // } // cout << endl; for(int i = 0; i <= n; i++) ile[i] = 0; for(int i = 0; i < n; i++) for(int j = 0; j < i; j++) if(tab[i][j]) ile[mac[i][j]]++; // cout << "ILEE" << endl; // for(int i = 0; i < n; i++){ // cout << ile[i] << ' '; // } // cout << endl; // cout << max_k << ' ' << k << endl; for(int i = n; i >= 0; i--){ if(max_k - ile[i] < k){ oznacz(i); ans = (ans + (ll)i*fast(n, KK))%mod; break; } else max_k -= ile[i]; } } cout << ans << '\n'; }