fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. //#pragma GCC optimize ("O3")
  5. //#pragma GCC target ("sse4")
  6.  
  7. #define SZ(x) ((int)x.size())
  8. #define ALL(V) V.begin(), V.end()
  9. #define L_B lower_bound
  10. #define U_B upper_bound
  11. #define pb push_back
  12.  
  13. using namespace std;
  14. template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
  15. template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
  16. const double PI = acos(-1);
  17. const int MAXN = (1 << 21);
  18.  
  19. struct complex_base
  20. {
  21. 	double x, y;
  22. 	complex_base(double _x = 0, double _y = 0) { x = _x; y = _y; }
  23. 	friend complex_base operator-(const complex_base &a, const complex_base &b) { return complex_base(a.x - b.x, a.y - b.y); }
  24. 	friend complex_base operator+(const complex_base &a, const complex_base &b) { return complex_base(a.x + b.x, a.y + b.y); }
  25. 	friend complex_base operator*(const complex_base &a, const complex_base &b) { return complex_base(a.x * b.x - a.y * b.y, a.y * b.x + b.y * a.x); }
  26. 	friend void operator/=(complex_base &a, const double &P) { a.x /= P; a.y /= P; }
  27. };
  28.  
  29. int bit_rev[MAXN];
  30. int last_n_fft = -1, ilast_n_fft = -1;
  31. complex_base root[MAXN], iroot[MAXN];
  32.  
  33. void fft(complex_base *a, int lg)
  34. {
  35. 	int n = (1 << lg);
  36. 	if(last_n_fft != n)
  37. 	{
  38. 		double ang = 2 * PI / n;
  39. 		for(int i = 0; i < (n >> 1); i++)
  40. 			root[i] = complex_base(cos(ang * i), sin(ang * i));
  41.  
  42. 		last_n_fft = n;
  43. 	}
  44.  
  45. 	for(int i = 1; i < n; i++)
  46. 	{
  47. 		bit_rev[i] = (bit_rev[i >> 1] >> 1) | ((i & 1) << (lg - 1));
  48. 		if(bit_rev[i] < i) swap(a[i], a[bit_rev[i]]);
  49. 	}
  50.  
  51. 	for(int len = 2; len <= n; len <<= 1)
  52. 	{
  53. 		int step = (n / len);
  54. 		for(int j = 0; j < (len >> 1); j++)
  55. 			for(int i = 0; i < n; i += len)
  56. 			{
  57. 				complex_base u = a[i + j], v = root[step * j] * a[i + j + (len >> 1)];
  58. 				a[i + j] = u + v;
  59. 				a[i + j + (len >> 1)] = u - v;
  60. 			}
  61. 	}
  62. }
  63.  
  64. void inv_fft(complex_base *a, int lg)
  65. {
  66. 	int n = (1 << lg);
  67. 	if(ilast_n_fft != n)
  68. 	{
  69. 		double ang = -2 * PI / n;
  70. 		for(int i = 0; i < (n >> 1); i++)
  71. 			iroot[i] = complex_base(cos(ang * i), sin(ang * i));
  72.  
  73. 		ilast_n_fft = n;
  74. 	}
  75.  
  76. 	for(int i = 1; i < n; i++)
  77. 	{
  78. 		bit_rev[i] = (bit_rev[i >> 1] >> 1) | ((i & 1) << (lg - 1));
  79. 		if(bit_rev[i] < i) swap(a[i], a[bit_rev[i]]);
  80. 	}
  81.  
  82. 	for(int len = 2; len <= n; len <<= 1)
  83. 	{
  84. 		int step = (n / len);
  85. 		for(int j = 0; j < (len >> 1); j++)
  86. 			for(int i = 0; i < n; i += len)
  87. 			{
  88. 				complex_base u = a[i + j], v = iroot[step * j] * a[i + j + (len >> 1)];
  89. 				a[i + j] = u + v;
  90. 				a[i + j + (len >> 1)] = u - v;
  91. 			}
  92. 	}
  93.  
  94. 	for(int i = 0; i < n; i++)
  95. 		a[i] /= n;
  96. }
  97.  
  98. complex_base A[MAXN], B[MAXN];
  99.  
  100. vector<int64_t> mult(vector<int64_t> a, vector<int64_t> b)
  101. {
  102. 	if(a.size() * b.size() <= 256)
  103. 	{
  104. 		vector<int64_t> ans(a.size() + b.size(), 0);
  105. 		for(int i = 0; i < (int)a.size(); i++)
  106. 			for(int j = 0; j < (int)b.size(); j++)
  107. 				ans[i + j] += a[i] * b[j];
  108.  
  109. 		return ans;
  110. 	}
  111.  
  112. 	int lg = 0; while((1 << lg) < (int)(a.size() + b.size())) ++lg;
  113. 	for(int i = 0; i < (1 << lg); i++) A[i] = B[i] = complex_base(0, 0);
  114. 	for(int i = 0; i < (int)a.size(); i++) A[i] = complex_base(a[i], 0);
  115. 	for(int i = 0; i < (int)b.size(); i++) B[i] = complex_base(b[i], 0);
  116.  
  117. 	fft(A, lg); fft(B, lg);
  118. 	for(int i = 0; i < (1 << lg); i++)
  119. 		A[i] = A[i] * B[i];
  120. 	inv_fft(A, lg);
  121.  
  122. 	vector<int64_t> ans(a.size() + b.size(), 0);
  123. 	for(int i = 0; i < (int)ans.size(); i++)
  124. 		ans[i] = (int64_t)(A[i].x + 0.5);
  125.  
  126. 	return ans;
  127. }
  128.  
  129. int n, L, R;
  130. vector<int> adj[MAXN];
  131.  
  132. void read()
  133. {
  134. 	cin >> n >> L >> R;
  135.  
  136. 	for(int i = 1; i <= n; i++)
  137. 		adj[i].clear();
  138.  
  139. 	for(int i = 0; i < n - 1; i++)
  140. 	{
  141. 		int u, v;
  142. 		cin >> u >> v;
  143. 		adj[u].push_back(v);
  144. 		adj[v].push_back(u);
  145. 	}
  146. }
  147.  
  148. int tr_sz[MAXN], cnt_vers;
  149. bool used[MAXN];
  150.  
  151. void pre_dfs(int u, int pr)
  152. {
  153. 	cnt_vers++;
  154. 	tr_sz[u] = 1;
  155. 	for(int v: adj[u])
  156. 		if(!used[v] && v != pr)
  157. 		{
  158. 			pre_dfs(v, u);
  159. 			tr_sz[u] += tr_sz[v];
  160. 		}
  161. }
  162.  
  163. int centroid(int u, int pr)
  164. {
  165. 	for(int v: adj[u])
  166. 		if(!used[v] && v != pr && tr_sz[v] > cnt_vers / 2)
  167. 			return centroid(v, u);
  168.  
  169. 	return u;
  170. }
  171.  
  172. int link[MAXN]; 
  173. vector<int64_t> cnt;
  174.  
  175. void dfs_add(int u, int pr, int dep = 0)
  176. {
  177. 	if(dep != 0)
  178. 		cnt[dep]++;
  179.  
  180. 	for(int v: adj[u])
  181. 		if(v != pr && !used[v])
  182. 			dfs_add(v, u, dep + 1);
  183. }
  184.  
  185. int64_t answer[MAXN];
  186.  
  187. void add_dfs1(int u, int pr, int dep = 0)
  188. {
  189. 	answer[dep]++;
  190. 	for(int v: adj[u])
  191. 		if(v != pr && !used[v])
  192. 			add_dfs1(v, u, dep + 1);
  193. }
  194.  
  195. vector<int64_t> get_cnt(int u, int pr, int d)
  196. {
  197. 	cnt.assign(tr_sz[u] + 1, 0);
  198. 	dfs_add(u, pr, d);
  199. 	return cnt;
  200. }
  201.  
  202. void decompose(int u, int pr = -1)
  203. {
  204. 	cnt_vers = 0;
  205. 	pre_dfs(u, u);
  206. 	int cen = centroid(u, u);
  207. 	link[cen] = pr;
  208.  
  209. 	used[cen] = true;
  210.  
  211. 	for(int v: adj[cen])
  212. 		if(!used[v]) 
  213. 			decompose(v, cen);
  214.  
  215. 	used[cen] = false;	
  216. 	pre_dfs(cen, cen);
  217.  
  218. 	vector<int64_t> answer_c(2 * cnt_vers + 42, 0);
  219. 	vector<int64_t> Cn = get_cnt(cen, cen, 0);
  220. 	Cn = mult(Cn, Cn);
  221. 	for(int i = 0; i < SZ(Cn); i++)
  222. 		answer_c[i] += Cn[i];
  223.  
  224. 	for(int v: adj[cen])
  225. 		if(!used[v])
  226. 		{
  227. 			add_dfs1(v, cen, 1);
  228. 			Cn = get_cnt(v, cen, 1);
  229.  
  230. 			Cn = mult(Cn, Cn);
  231. 			for(int i = 0; i < SZ(Cn); i++)
  232. 				answer_c[i] -= Cn[i];
  233. 		}
  234.  
  235. 	for(int i = 0; i < SZ(answer_c); i++)
  236. 		answer[i] += answer_c[i] / 2ll;
  237. }
  238.  
  239. void solve()
  240. {
  241. 	for(int i = 0; i <= n; i++)
  242. 		answer[i] = 0;
  243.  
  244. 	decompose(1);
  245.  
  246. 	int64_t ans = 0;
  247. 	for(int i = 0; i <= n - 1; i++)
  248. 	{
  249. 		int c = n - 1 - i;
  250. 		if(L <= c && c <= R)
  251. 			ans += answer[i];
  252. 	}
  253.  
  254. 	cout << ans << endl;
  255. }
  256.  
  257. int main()
  258. {
  259. 	ios_base::sync_with_stdio(false);
  260. 	cin.tie(NULL);
  261. 	freopen("awesome.in", "r", stdin);
  262.  
  263. 	int T;
  264. 	cin >> T;
  265.  
  266. 	while(T--)
  267. 	{
  268. 		read();
  269. 		solve();
  270. 	}
  271.  
  272. 	return 0;
  273. }
Runtime error #stdin #stdout #stderr 0.02s 238464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::ios_base::failure[abi:cxx11]'
  what():  basic_filebuf::underflow error reading the file: iostream error
https://ideone.com/VIyWM9
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!