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
| #include <bits/stdc++.h> #define dbg(x) std::cerr << #x << " = " << x << endl #define int long long using namespace std; typedef long long ll;
const ll N = 1000 + 10; const ll mod = (ll)(1e9 + 7); ll dp[N][N], sum[N], sum1[N][N], sz[N], m, n;
vector <ll> pool[N][N]; vector <pair <ll, ll> > g[N];
void dfs(int u, int f) { for(int i = 1; i <= m; i++) dp[u][i] = 1;
for(auto x: g[u]) { int v = x.first, w = x.second; if(v == f) continue; dfs(v, u); for(int j = 1; j <= m; j++) { int now = sum[v]; for(auto k: pool[w][j]) now = (now - dp[v][k] + mod) % mod; dp[u][j] = dp[u][j] * now % mod; } } for(int i = 1; i <= m; i++) sum[u] = (sum[u] + dp[u][i]) % mod; } signed main() { scanf("%d%d", &n, &m); for(int i = 1; i < n; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); g[u].push_back({v, w}); g[v].push_back({u, w}); }
for(int k = 1; k <= m; k++) for(int i = 1; i <= m; i++) for(int j = k; j <= m; j += k) if(__gcd(i, j) == k) pool[k][i].push_back(j);
dfs(1, 0);
ll ans = 0; for(int i = 1; i <= m; i++) ans = (ans + dp[1][i]) % mod; cout << ans << endl; return 0; }
|