fork download
copy 
  1. #include <functional>
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <utility>
  5. #include <sstream>
  6. #include <iomanip>
  7. #include <numeric>
  8. #include <cstdlib>
  9. #include <cstring>
  10. #include <climits>
  11. #include <cstring>
  12. #include <vector>
  13. #include <cstdio>
  14. #include <string>
  15. #include <stack>
  16. #include <deque>
  17. #include <queue>
  18. #include <cmath>
  19. #include <map>
  20. #include <set>
  21. //#include <bits/stdc++.h>
  22. //#define pb push_back
  23. //#define pf push_front
  24. //#define ppb pop_back
  25. //#define ppf pop_front
  26. #define lwb lower_bound
  27. #define upb upper_bound
  28. #define X first
  29. #define Y second
  30. //#define FOR(i,j,k) for(int i = j; i < (int)(k); i++)
  31. //#define FORV(i, v) FOR(i, 0, ((v).size()))
  32. //#define sz(a) (int)((a).size())
  33. //#define all(a) a.begin() , a.end()
  34. #define coud(a,b) cout<<fixed << setprecision((b)) << (a)
  35. #define L(x) ((x)<<1)
  36. #define R(x) (((x)<<1)+1)
  37. //#define int long long
  38. #define double long double
  39. #define joon ios :: sync_with_stdio(false)
  40. //#define cin fin
  41. //#define cout fout
  42.  
  43. using namespace std;
  44.  
  45. typedef pair<int, int> pii;
  46. typedef long long ll;
  47. const double pi = acos(-1);
  48. const double eps = 1e-7;
  49. const int MAXN=100000+100;
  50. const int mod=1000*1000*1000 +7;
  51. vector< pair<int,int> > N[MAXN];
  52. long long l[MAXN],r[MAXN];
  53. long long int f[MAXN];
  54. long long int s[MAXN];
  55. int n;
  56. bool mark[MAXN];
  57. int dp[MAXN];
  58. int pre[MAXN];
  59.  
  60. inline void dfs(int v,int e)
  61. {
  62. 	mark[v]=1;
  63. 	s[v]=1;
  64. 	for(int i=0;i<(int)N[v].size();i++)
  65. 	{
  66. 		int u=N[v][i].first;
  67. 		int ee=N[v][i].second;
  68. 		if( mark[ u ]==0 )
  69. 		{
  70. 			dfs( u , ee );
  71. 			s[v]+=s[ u ];
  72. 		}
  73. 	}
  74. 	f[e]= s[v]*n - s[v]*s[v] ;
  75. 	return ;
  76. }
  77.  
  78. int main()
  79. {
  80. 	int k;
  81. 	scanf("%d%d" , &n , &k );
  82. 	for(int i=1;i<n;i++)
  83. 	{
  84. 		int v,u,aa,bb;
  85. 		scanf("%d%d%d%d" , &v , &u , &aa , &bb );
  86. 		l[i]=aa;
  87. 		r[i]=bb;
  88. 		N[v].push_back( make_pair(u,i) );
  89. 		N[u].push_back( make_pair(v,i) );
  90. 	}
  91. 	long long flgg=(n-1)*(n-1);
  92. 	if( flgg > k )
  93. 	{
  94. 		cout<<0<<endl;
  95. 		return 0;
  96. 	}
  97. 	dfs(1,0);
  98. 	for(int i=1;i<n;i++)
  99. 		k-=(f[i]*l[i]);
  100. 	if( k < 0 )
  101. 	{
  102. 		cout<<0<<endl;
  103. 		return 0;
  104. 	}
  105. 	if( n==1 )
  106. 	{
  107. 		cout<<1<<endl;
  108. 		return 0;
  109. 	}
  110. 	for(int i=1;i<n;i++)
  111. 		dp[0]=1;
  112. 	for(int i=l[1]+1;i<=r[1];i++)
  113. 		if( (i-l[1])*f[1] <=k )
  114. 			dp[ (i-l[1])*f[1] ]=1;
  115. 	for(int i=0;i<=k;i++)
  116. 	{
  117. 		if( i-f[2] < 0 )
  118. 			pre[i]=dp[i]%mod;
  119. 		else
  120. 			pre[i]=( pre[i-f[2]]+dp[i] )%mod;
  121. 	}
  122. 	for(int i=2;i<n;i++)
  123. 	{
  124. 		memset( dp , 0 , sizeof(dp) );
  125. 		for(int j=0;j<=k;j++)
  126. 		{
  127. 			long long x1=0;
  128. 			if( j - (r[i]-l[i]+1)*f[i] >= 0 )
  129. 				x1=pre[ j-(r[i]-l[i]+1)*f[i] ]%mod;
  130. 			dp[j]=( pre[j]-x1+mod  )%mod;
  131. 		}
  132. 		if( i < n-1 )
  133. 		{
  134. 			for(int j=0;j<=k;j++)
  135. 			{
  136. 				if( j-f[i+1] < 0 )
  137. 					pre[j]=dp[j]%mod;
  138. 				else
  139. 					pre[j]=( pre[j-f[i+1]]+dp[j] )%mod;
  140. 			}
  141. 		}
  142. 	}
  143. 	long long ans=0;
  144. 	for(int i=0;i<=k;i++)
  145. 		ans=( ans + dp[i] )%mod;
  146. 	cout<<ans<<endl;
  147.  
  148. 	return 0;
  149. }
  150.  
  151.  
Success #stdin #stdout 0s 8600KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/WOZfbg
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!