fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. using db = long double;  // or double, if TL is tight
  6. using str = string;      // yay python!
  7.  
  8. using pi = pair<int, int>;
  9. using pl = pair<ll, ll>;
  10. using pd = pair<db, db>;
  11.  
  12. using vi = vector<int>;
  13. using vb = vector<bool>;
  14. using vl = vector<ll>;
  15. using vd = vector<db>;
  16. using vs = vector<str>;
  17. using vpi = vector<pi>;
  18. using vpl = vector<pl>;
  19. using vpd = vector<pd>;
  20.  
  21. #define tcT template <class T
  22. #define tcTU tcT, class U
  23. // ^ lol this makes everything look weird but I'll try it
  24. tcT > using V = vector<T>;
  25. tcT, size_t SZ > using AR = array<T, SZ>;
  26. tcT > using PR = pair<T, T>;
  27.  
  28. // pairs
  29. #define mp make_pair
  30. #define f first
  31. #define s second
  32.  
  33. // vectors
  34. // oops size(x), rbegin(x), rend(x) need C++17
  35. #define sz(x) int((x).size())
  36. #define bg(x) begin(x)
  37. #define all(x) bg(x), end(x)
  38. #define rall(x) x.rbegin(), x.rend()
  39. #define sor(x) sort(all(x))
  40. #define rsz resize
  41. #define ins insert
  42. #define ft front()
  43. #define bk back()
  44. #define pb push_back
  45. #define eb emplace_back
  46. #define pf push_front
  47. #define rtn return
  48.  
  49. #define lb lower_bound
  50. #define ub upper_bound
  51. tcT > int lwb(V<T> &a, const T &b) { return int(lb(all(a), b) - bg(a)); }
  52.  
  53. // loops
  54. #define FOR(i, a, b) for (int i = (a); i < (b); ++i)
  55. #define F0R(i, a) FOR(i, 0, a)
  56. #define ROF(i, a, b) for (int i = (b) - 1; i >= (a); --i)
  57. #define R0F(i, a) ROF(i, 0, a)
  58. #define EACH(a, x) for (auto &a : x)
  59.  
  60. const int MOD = 1e9 + 7;  // 998244353;
  61. const int MX = 2e5 + 5;
  62. const ll INF = 1e18;  // not too close to LLONG_MAX
  63. const db PI = acos((db)-1);
  64. const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};  // for every grid problem!!
  65. mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
  66. template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
  67.  
  68. // bitwise ops
  69. // also see https://g...content-available-to-author-only...u.org/onlinedocs/gcc/Other-Builtins.html
  70. constexpr int pct(int x) { return __builtin_popcount(x); }  // # of bits set
  71. constexpr int bits(int x) {  // assert(x >= 0); // make C++11 compatible until
  72. 	                         // USACO updates ...
  73. 	return x == 0 ? 0 : 31 - __builtin_clz(x);
  74. }  // floor(log2(x))
  75. constexpr int p2(int x) { return 1 << x; }
  76. constexpr int msk2(int x) { return p2(x) - 1; }
  77.  
  78. ll cdiv(ll a, ll b) {
  79. 	return a / b + ((a ^ b) > 0 && a % b);
  80. }  // divide a by b rounded up
  81. ll fdiv(ll a, ll b) {
  82. 	return a / b - ((a ^ b) < 0 && a % b);
  83. }  // divide a by b rounded down
  84.  
  85. tcT > bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }  // set a = min(a,b)
  86. tcT > bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
  87.  
  88. tcTU > T fstTrue(T lo, T hi, U f) {
  89. 	hi++;
  90. 	assert(lo <= hi);  // assuming f is increasing
  91. 	while (lo < hi) {  // find first index such that f is true
  92. 		T mid = lo + (hi - lo) / 2;
  93. 		f(mid) ? hi = mid : lo = mid + 1;
  94. 	}
  95. 	return lo;
  96. }
  97. tcTU > T lstTrue(T lo, T hi, U f) {
  98. 	lo--;
  99. 	assert(lo <= hi);  // assuming f is decreasing
  100. 	while (lo < hi) {  // find first index such that f is true
  101. 		T mid = lo + (hi - lo + 1) / 2;
  102. 		f(mid) ? lo = mid : hi = mid - 1;
  103. 	}
  104. 	return lo;
  105. }
  106. tcT > void remDup(vector<T> &v) {  // sort and remove duplicates
  107. 	sort(all(v));
  108. 	v.erase(unique(all(v)), end(v));
  109. }
  110. tcTU > void erase(T &t, const U &u) {  // don't erase
  111. 	auto it = t.find(u);
  112. 	assert(it != end(t));
  113. 	t.erase(it);
  114. }  // element that doesn't exist from (multi)set
  115.  
  116. // INPUT
  117. #define tcTUU tcT, class... U
  118. tcT > void re(complex<T> &c);
  119. tcTU > void re(pair<T, U> &p);
  120. tcT > void re(V<T> &v);
  121. tcT, size_t SZ > void re(AR<T, SZ> &a);
  122.  
  123. tcT > void re(T &x) { cin >> x; }
  124. void re(double &d) {
  125. 	str t;
  126. 	re(t);
  127. 	d = stod(t);
  128. }
  129. void re(long double &d) {
  130. 	str t;
  131. 	re(t);
  132. 	d = stold(t);
  133. }
  134. tcTUU > void re(T &t, U &...u) {
  135. 	re(t);
  136. 	re(u...);
  137. }
  138.  
  139. tcT > void re(complex<T> &c) {
  140. 	T a, b;
  141. 	re(a, b);
  142. 	c = {a, b};
  143. }
  144. tcTU > void re(pair<T, U> &p) { re(p.f, p.s); }
  145. tcT > void re(V<T> &x) { EACH(a, x) re(a); }
  146. tcT, size_t SZ > void re(AR<T, SZ> &x) { EACH(a, x) re(a); }
  147. tcT > void rv(int n, V<T> &x) {
  148. 	x.rsz(n);
  149. 	re(x);
  150. }
  151.  
  152. // TO_STRING
  153. #define ts to_string
  154. str ts(char c) { return str(1, c); }
  155. str ts(const char *s) { return (str)s; }
  156. str ts(str s) { return s; }
  157. str ts(bool b) {
  158. 	// #ifdef LOCAL
  159. 	// 	return b ? "true" : "false";
  160. 	// #else
  161. 	return ts((int)b);
  162. 	// #endif
  163. }
  164. tcT > str ts(complex<T> c) {
  165. 	stringstream ss;
  166. 	ss << c;
  167. 	return ss.str();
  168. }
  169. str ts(V<bool> v) {
  170. 	str res = "{";
  171. 	F0R(i, sz(v)) res += char('0' + v[i]);
  172. 	res += "}";
  173. 	return res;
  174. }
  175. template <size_t SZ> str ts(bitset<SZ> b) {
  176. 	str res = "";
  177. 	F0R(i, SZ) res += char('0' + b[i]);
  178. 	return res;
  179. }
  180. tcTU > str ts(pair<T, U> p);
  181. tcT > str ts(T v) {  // containers with begin(), end()
  182. #ifdef LOCAL
  183. 	bool fst = 1;
  184. 	str res = "{";
  185. 	for (const auto &x : v) {
  186. 		if (!fst) res += ", ";
  187. 		fst = 0;
  188. 		res += ts(x);
  189. 	}
  190. 	res += "}";
  191. 	return res;
  192. #else
  193. 	bool fst = 1;
  194. 	str res = "";
  195. 	for (const auto &x : v) {
  196. 		if (!fst) res += " ";
  197. 		fst = 0;
  198. 		res += ts(x);
  199. 	}
  200. 	return res;
  201.  
  202. #endif
  203. }
  204. tcTU > str ts(pair<T, U> p) {
  205. #ifdef LOCAL
  206. 	return "(" + ts(p.f) + ", " + ts(p.s) + ")";
  207. #else
  208. 	return ts(p.f) + " " + ts(p.s);
  209. #endif
  210. }
  211.  
  212. // OUTPUT
  213. tcT > void pr(T x) { cout << ts(x); }
  214. tcTUU > void pr(const T &t, const U &...u) {
  215. 	pr(t);
  216. 	pr(u...);
  217. }
  218. void ps() { pr("\n"); }  // print w/ spaces
  219. tcTUU > void ps(const T &t, const U &...u) {
  220. 	pr(t);
  221. 	if (sizeof...(u)) pr(" ");
  222. 	ps(u...);
  223. }
  224.  
  225. // DEBUG
  226. void DBG() { cerr << "]" << endl; }
  227. tcTUU > void DBG(const T &t, const U &...u) {
  228. 	cerr << ts(t);
  229. 	if (sizeof...(u)) cerr << ", ";
  230. 	DBG(u...);
  231. }
  232. #ifdef LOCAL  // compile with -DLOCAL, chk -> fake assert
  233. #define dbg(...)                                                                       \
  234. 	cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
  235. #define chk(...)                                                                       \
  236. 	if (!(__VA_ARGS__))                                                                \
  237. 		cerr << "Line(" << __LINE__ << ") -> function(" << __FUNCTION__                \
  238. 		     << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n",                   \
  239. 		    exit(0);
  240. #else
  241. #define dbg(...) 0
  242. #define chk(...) 0
  243. #endif
  244.  
  245. void setPrec() { cout << fixed << setprecision(15); }
  246. void unsyncIO() { cin.tie(0)->sync_with_stdio(0); }
  247. // FILE I/O
  248. void setIn(str s) { freopen(s.c_str(), "r", stdin); }
  249. void setOut(str s) { freopen(s.c_str(), "w", stdout); }
  250. void setIO(str s = "") {
  251. 	unsyncIO();
  252. 	setPrec();
  253. 	// cin.exceptions(cin.failbit);
  254. 	// throws exception when do smth illegal
  255. 	// ex. try to read letter into int
  256. 	if (sz(s)) setIn(s + ".in"), setOut(s + ".out");  // for USACO
  257. }
  258.  
  259. int max_len;
  260. ll mul = 1;
  261. ll ans;
  262. int N, K1, K2;
  263. vi adj[MX];
  264.  
  265. int get_prefix(const deque<int> &a, int mx) {
  266. 	if (mx < 0) return 0;
  267. 	if (mx + 1 >= sz(a)) return a[0];
  268. 	return a[0] - a[mx + 1];
  269. }
  270.  
  271. void comb(deque<int> &a, deque<int> &b) {
  272. 	if (sz(a) < sz(b)) swap(a, b);
  273. 	F0R(i, sz(b) - 1) b[i] -= b[i + 1];
  274. 	F0R(i, sz(b))
  275. 	ans += (ll)b[i] * (get_prefix(a, K2 - i) - get_prefix(a, K1 - 1 - i));
  276. 	R0F(i, sz(b) - 1) b[i] += b[i + 1];
  277. 	F0R(i, sz(b)) a[i] += b[i];
  278. }
  279.  
  280. deque<int> dfs(int x, int p) {  // each deque stores prefix sums
  281. 	deque<int> res{1};
  282. 	EACH(y, adj[x]) if (y != p) {
  283. 		deque<int> a = dfs(y, x);
  284. 		a.push_front(a.ft);
  285. 		comb(res, a);
  286. 	}
  287. 	return res;
  288. }
  289.  
  290. int main() {
  291. 	setIO();
  292. 	re(N, K1, K2);
  293. 	F0R(i, N - 1) {
  294. 		int a, b;
  295. 		re(a, b);
  296. 		adj[a].pb(b), adj[b].pb(a);
  297. 	}
  298. 	max_len = K1 - 1, mul = -1;
  299. 	dfs(1, 0);
  300. 	ps(ans);
  301. }
Success #stdin #stdout 0.01s 8456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/UmZeHa
language:
C++14 (gcc 8.3)
created:
7 hours 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!