<题目链接 https://vjudge.net/contest/280094#problem/D>
题目大意:
一颗无向无环树, 有 n 个顶点, 求其中距离为 k 的点对数是多少,(u,v)与 (v,u) 为同一点对.
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- using namespace std;
- #define N int(5e4+10)
- int n,k,ans,cnt;
- int dp[N][510],head[N];
- struct Edge{
- int to,nxt;
- }edge[N<<1];
- void init(){
- cnt=0;ans=0;
- memset(head,-1,sizeof(head));
- memset(dp,0,sizeof(dp));
- }
- void addedge(int u,int v){
- edge[cnt].to=v,edge[cnt].nxt=head[u];
- head[u]=cnt++;
- }
- void dfs(int u,int fa){
- dp[u][0]=1; //dp[i][j]表示以 u 为根的子树中, 距 u 的距离为 j 的点的数量
- for(int i=head[u];~i;i=edge[i].nxt){
- int v=edge[i].to;
- if(v==fa)continue;
- dfs(v,u);
- for(int j=0;j<k;j++)ans+=dp[u][j]*dp[v][k-j-1];
- for(int j=1;j<=k;j++)dp[u][j]+=dp[v][j-1];
- }
- }
- int main(){
- while(~scanf("%d%d",&n,&k)){
- init();
- for(int i=1;i<n;i++){
- int u,v;scanf("%d%d",&u,&v);
- addedge(u,v);addedge(v,u);
- }
- dfs(1,-1);
- printf("%d\n",ans);
- }
- }
- 2019-02-07
来源: http://www.bubuko.com/infodetail-2947217.html