#include<cstdio> #include<cmath> #include<iostream> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; struct Edge{int next,to;}ed[6010]; int n,p,q,num_edge,head[3010],dis[3010],dep[3010],fa[3010][21],cnt[3010],sum[3010],cul[3010]; ll ans; bool vis[3010]; void Add(int f,int t) { ed[++num_edge].next=head[f]; ed[num_edge].to=t; head[f]=num_edge; } void Pre(int x,int dept,int dist) { vis[x]=1; dep[x]=dept; dis[x]=dist; for(int i=1;i<=13;i++) { fa[x][i]=fa[fa[x][i-1]][i-1]; } for(int i=head[x];i;i=ed[i].next) { int t=ed[i].to; if(vis[t]) continue; fa[t][0]=x; Pre(t,dept+1,dist+1); } vis[x]=0; } int LCA(int x,int y) { if(dep[x]<dep[y]) { swap(x,y); } for(int i=13;i>=0;i--) { if(dep[fa[x][i]]>=dep[y]) x=fa[x][i]; if(x==y) return x; } for(int i=13;i>=0;i--) { if(fa[x][i]!=fa[y][i]) { x=fa[x][i]; y=fa[y][i]; } } return fa[x][0]; } void Cul(int x) { vis[x]=1; for(int i=head[x];i;i=ed[i].next) { int t=ed[i].to; if(vis[t]) continue; Cul(t); sum[x]+=sum[t]; cul[x]+=cul[t]; } sum[x]+=cnt[x]; vis[x]=0; } void FPX(int x,int lian,int num,int ffa) { if(num==p) { lian-=cnt[x]; int lca=LCA(ffa,x); ans+=(sum[lca]+lian); ans+=(sum[1]-sum[lca]-cul[lca]); return; } vis[x]=1; for(int i=head[x];i;i=ed[i].next) { int t=ed[i].to; if(vis[t]) continue; FPX(t,lian-cnt[x],num+1,ffa); } vis[x]=0; } int main() { scanf("%d%d%d",&n,&p,&q); for(int i=1;i<=n-1;i++) { int f,t; scanf("%d%d",&f,&t); Add(f,t); Add(t,f); } Pre(1,1,0); for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { int lca=LCA(i,j); if(dis[i]+dis[j]-2*dis[lca]==q) { cnt[lca]+=2; cul[i]+=2; cul[j]+=2; cul[lca]-=4; } } } Cul(1); for(int i=1;i<=n;i++) { FPX(i,0,0,i); } printf("%lld",ans); return 0; }
全部评论
(2) 回帖