// compile: make data
// run: time ./data < mid.in
#include <bits/stdc++.h>
using namespace std;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifdef LOCAL
#include <debug/codeforces.h>
#define debug(x...) _debug_print(#x, x);
#define Debug(x...) _debug_print_format(#x, x);
std::ifstream terminal("/dev/tty");
#define PP cerr<<"\033[1;30mpause...\e[0m",terminal.ignore();
#else
#define debug(x...)
#define Debug(x...)
#define PP
#endif
template<typename...Args> void print_(Args...args){((cout<<args<<" "),...)<<endl;}
#define VI vector<int>
#define VII vector<vector<int>>
#define VIII vector<vector<vector<int>>>
#define rep(i,a,b) for(int i=(a);i<(int)(b);++i)
#define sz(v) ((int)(v).size())
#define print(...) print_(__VA_ARGS__);
#define FIND(a, x) ((find(a.begin(),a.end(),(x))!=a.end())?1:0)
#define cmin(x,...) x=min({(x), __VA_ARGS__})
#define cmax(x,...) x=max({(x), __VA_ARGS__})
#define INTMAX (int)(9223372036854775807)
#define INF (int)(1152921504606846976)
#define NaN (int)(0x8b88e1d0595d51d1)
#define double long double
#define MAXN 200010
int n, A, B;
vector<int> e[MAXN];
int tsize[MAXN], depth[MAXN], height[MAXN];
bool removed[MAXN];
void builddfs(int u, int pre) {
tsize[u] = 1;
depth[u] = !~pre ? 0 : depth[pre] + 1;
height[u] = 1;
for (int v: e[u]) {
if (v == pre || removed[v]) continue;
builddfs(v, u);
tsize[u] += tsize[v];
cmax(height[u], height[v] + 1);
}
}
int centroid(int r) {
// builddfs(r, -1);
int N = tsize[r];
if (N <= 2) return r;
int p = -1;
for (int x = r; ; ) {
int maxsz = -INF, maxnode = -1;
for (auto y: e[x]) if (y != p && !removed[y] && tsize[y] > maxsz) maxsz = tsize[y], maxnode = y;
if (maxsz <= N / 2) return x;
p = x;
x = maxnode;
}
return r;
}
int cur[MAXN], cnt[MAXN];
long long sum[MAXN];
long long getsum(int i, int l, int r, int m) {
if (r >= m) r = m-1;
if (l < 0) l = 0;
if (l > r) return 0;
return sum[r] - (l ? sum[l-1] : 0) - (i<=r && i>=l);
}
long long calc(int *a, int m) {
memset(sum, 0, sizeof(long long)*m);
sum[0] = a[0]; rep(i, 1, m) sum[i] = sum[i-1] + a[i];
long long res = 0;
rep(i, 0, m) res += a[i] * getsum(i, A-i, B-i, m);
return res / 2;
};
long long answer = 0;
int qx[MAXN], qy[MAXN];
void getvs(int *a, int u, int r, int base) {
int head = 0, tail = 0;
qx[0] = u, qy[0] = r;
while (head <= tail) {
int x = qx[head], p = qy[head++];
if (depth[x]-base > B) continue;
++a[depth[x]-base];
for (auto y: e[x]) if (!removed[y] && y != p) qx[++tail] = y, qy[tail] = x;
}
};
void cddfs(int x) {
int c = centroid(x);
if (c != x) builddfs(c, -1);
int base = depth[c];
if (tsize[c] < A/2) return;
memset(cnt, 0, sizeof(int)*height[c]);
cnt[0] = 1;
for (auto y: e[c]) if(!removed[y]) {
memset(cur, 0, sizeof(int)*height[c]);
getvs(cur, y, c, base);
answer -= calc(cur, height[c]);
rep(i, 0, height[c]) cnt[i] += cur[i];
}
answer += calc(cnt, height[c]);
removed[c] = 1;
for (auto v: e[c]) if (!removed[v]) cddfs(v);
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
scanf("%d%d%d", &n, &A, &B);
rep(i, 0, n-1) {
int u, v; scanf("%d%d", &u, &v);
e[u-1].push_back(v-1);
e[v-1].push_back(u-1);
}
builddfs(0, -1);
cddfs(0);
printf("%lld\n", answer);
return 0;
}
No Comments