Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Code
- #include <bits/stdc++.h>
- using namespace std;
- const int MAX = 2e5+50;
- int n, k1, k2;
- int64_t ans;
- vector<int> gr[MAX];
- int dad[MAX], sub[MAX];
- bool rem[MAX];
- int b[MAX];
- void init(int sz) {
- for (int idx = 1; idx <= sz+1; ++idx)
- b[idx] = 0;
- }
- void add(int idx, int val, int sz) {
- for (++idx; idx <= sz+1; idx += (idx & -idx)) {
- b[idx] += val;
- }
- }
- int64_t sum(int idx, int sz) {
- if (idx < 0) return 0;
- idx = min(idx, sz);
- int64_t res = 0;
- for (++idx; idx > 0; idx -= (idx & -idx)) {
- res += b[idx];
- }
- return res;
- }
- int64_t query(int l, int r, int sz) {
- return sum(r, sz)-sum(l-1, sz);
- }
- int dfs(int u, int par) {
- sub[u] = 1;
- for (int to : gr[u]) if (to != par and !rem[to]) {
- sub[u] += dfs(to, u);
- }
- return sub[u];
- }
- int centroid(int u, int par, int sz) {
- for (int to : gr[u])
- if (to != par and !rem[to] and sub[to] > sz/2)
- return centroid(to, u, sz);
- return u;
- }
- void getChildren(int u, int par, int d, vector<int> &v) {
- v.push_back(d);
- for (int to : gr[u]) {
- if (!rem[to] and to != par) {
- getChildren(to, u, d+1, v);
- }
- }
- }
- int decomp(int u, int par) {
- int sz = dfs(u, par);
- int c = centroid(u, par, sz);
- if (par == -1)
- par = c;
- rem[c] = true;
- dad[c] = par;
- init(sz);
- add(0, 1, sz);
- for (int to : gr[c]) if (!rem[to]) {
- vector<int> v;
- getChildren(to, c, 1, v);
- for (int x : v) {
- ans += query(k1-x, k2-x, sz);
- }
- for (int x : v) {
- add(x, 1, sz);
- }
- }
- for (int to : gr[c]) if (!rem[to])
- decomp(to, c);
- return c;
- }
- int main() {
- cin.tie(0)->sync_with_stdio(0);
- cin >> n >> k1 >> k2;
- for (int i = 0, a, b; i < n-1; ++i) {
- cin >> a >> b, --a, --b;
- gr[a].push_back(b);
- gr[b].push_back(a);
- }
- decomp(0, -1);
- cout << ans << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment