Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.0 kB
2
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using LL = long long;

/*....................................................................*/ 

/*....................................................................*/ 

const int N = 2e5 + 5;
vector <int> T[N];
int k1, k2;
LL ans = 0;

namespace bit {
    int a[N];
    void add(int x, int val) {
        for(; x < N; x |= (x + 1)) a[x] += val;
    }
    int sum(int x) {
        int ans = 0;
        for(; x >= 0; x = (x & (x + 1)) - 1) ans += a[x];
        return ans;
    }
    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
}

namespace ctrd {
    int sz[N], cnt[N], mx;
    bool blk[N];

    int szCalc(int u, int p = -1) {
        sz[u] = 1;
        for(int v: T[u]) {
            if(v == p or blk[v]) continue;
            sz[u] += szCalc(v, u);
        }
        return sz[u];
    }
    int getCentroid(int u, int s, int p = -1) {
        for(int v: T[u]) {
            if(v == p or blk[v]) continue;
            if(sz[v] * 2 >= s) return getCentroid(v, s, u);
        }
        return u;
    }
    void dfs(int u, int p = -1, int d = 1) {
        mx = max(mx, d);
        cnt[d]++;
        for(int v: T[u]) {
            if(blk[v] or v == p) continue;
            dfs(v, u, d + 1);
        }
    }
    void solve(int u) {
        for(int v: T[u]) {
            if(blk[v]) continue;
            mx = 0;
            dfs(v, u);
            int _mx = min(mx, k2);

        }
    }
    void decompose(int u, int p = -1) {
        szCalc(u);
        int c = getCentroid(u, sz[u]);
        solve(c);
        blk[c] = 1;
        for(int v: T[c]) {
            if(!blk[v]) decompose(v, c);
        }
    }
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    int n;
    cin >> n >> k1 >> k2;
    for(int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        T[u].push_back(v);
        T[v].push_back(u);
    }

    ctrd :: decompose(1, k);
    cout << ans << '\n';
}