Untitled
plain_text
2 months ago
2.0 kB
1
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'; }