首页 > 代码库 > codeforces161D - Distance in Tree 树形dp

codeforces161D - Distance in Tree 树形dp

2024-07-15 14:06:33   221人阅读

题意：给你一棵树，问你树中距离为k的有多少种情况。

解题思路：树形dp  维护每个节点（1-K）深度的情况，

解题代码：

 1 // File Name: 161d.cpp 2 // Author: darkdream 3 // Created Time: 2014年08月03日 星期日 19时20分10秒 4  5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 #define LL long long25 26 using namespace std;27 28 vector<int> a[50004];29 int m[50005][500];30 int visit[50004];31 int n , k ;32 LL ans = 0 ;33 void dfs(int t)34 {35     int lt = a[t].size();36     m[t][0] = 1; 37     for(int i= 0 ;i < lt ;i ++)38     {39         int tt = a[t][i];40         if(!visit[tt])41         {42             visit[tt] = 1;43             dfs(tt);44             for(int j =0 ;j < k;j ++)45                 ans += m[t][k-j-1] * m[tt][j];46             for(int j = 0 ;j < k;j ++)47             {48                 m[t][j+1] += m[tt][j];49             }50         }51     }52 }53 int main(){54     scanf("%d %d",&n,&k);55     int ta,tb;56     memset(m,0,sizeof(m));57     memset(visit,0,sizeof(visit));58     for(int i =1 ;i <= n-1;i ++)59     {60         scanf("%d %d",&ta,&tb);61         a[ta].push_back(tb);62         a[tb].push_back(ta);63     }64     visit[1] = 1; 65     dfs(1);66     printf("%I64d\n",ans);67     return 0;68 }
View Code

 


联系
我们