Untitled
unknown
plain_text
3 months ago
1.2 kB
4
Indexable
#include <bits/stdc++.h> #pragma GCC optimize ("O3") #pragma GCC optimize ("Ofast") #define ll long long #define pb push_back using namespace std; const int M = 1e5 + 10; const int p = 1e9 + 7; int n; ll k; ll mul[M]; int r[M], l[M]; vector <pair<int, int>> adj[M]; ll mod(ll x){ return x % p; } ll dfs(int v, int p){ int sum = 1; for(auto [u, ind] : adj[v]){ if(u != p){ ll x = dfs(u, v); sum += x; mul[ind + 1] = mod(x * (n - x)); } } return sum; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; for(int i = 0; i < n - 1; i++){ int v, u; cin >> v >> u >> l[i + 1] >> r[i + 1]; adj[v].pb({u, i}); adj[u].pb({v, i}); } if(n > 317){ cout << 0 << endl; return 0; } dfs(1, 0); for(int i = 1; i < n; i++) k -= mul[i] * l[i]; if(k < 0){ cout << 0 << endl; return 0; } for(int i = 1; i < n; i++) r[i] -= l[i]; int dp[n][k + 1] = {}; for(int j = 0; j <= k; j++) dp[0][j] = 1; for(int i = 0; i < n; i++) dp[i][0] = 1; for(int i = 1; i < n; i++) for(ll j = 1; j <= k; j++) for(ll x = 0; x <= r[i]; x++){ if(j >= x*mul[i]) dp[i][j] = mod(dp[i][j] + dp[i - 1][j - x*mul[i]]); else break; } cout << dp[n - 1][k] << endl; return 0; }
Editor is loading...
Leave a Comment