Codeforces 161 D Distance in Tree 树形DP

题目大意：给出一棵n个节点的树，统计树中长度为k的路径的条数（1<=n<=50000 ,1<=k<=500）；

题目分析：设dp[i][j]表示以i作为长度为j的路径其中一个点的方案数。转移：dp[u][j]+=dp[v][j-1];  方案计数：ans+=dp[v][j]*dp[u][k-j-1];

复制代码#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<functional> #include<cmath> #include<cctype> #include<cassert> #include<climits> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define ForD(i,n) for(int i=n;i;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define RepD(i,n) for(int i=n;i>=0;i--) #define MEM(a) memset(a,0,sizeof(a)) #define MEMI(a) memset(a,127,sizeof(a)) #define MEMi(a) memset(a,128,sizeof(a)) #define INF (2139062143) #define phiF (1000000006) #define MAXN (1000000+10) typedef long long LL; struct info{ int to,next; }e[100005]; int tot,first[100005],dp[50005][505],k,ans,n,x,y; void add(int u,int v){ tot++; e[tot].to=v; e[tot].next=first[u]; first[u]=tot; } void dfs(int u,int fa){ dp[u][0]=1; for (int p=first[u];p;p=e[p].next){ int v=e[p].to; if (v==fa) continue; dfs(v,u); Rep (j,k) ans+=dp[v][j]*dp[u][k-j-1]; For (j,k) dp[u][j]+=dp[v][j-1]; } } int main(){ scanf("%d%d",&n,&k); For (i,n-1){ scanf("%d%d",&x,&y); add(x,y); add(y,x); } dfs(1,0); printf("%d",ans); }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
#include<cassert>
#include<climits>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define INF (2139062143)
#define phiF (1000000006)
#define MAXN (1000000+10)
typedef long long LL;

struct info{
	int to,next;
}e[100005];

int tot,first[100005],dp[50005][505],k,ans,n,x,y;

void add(int u,int v){
	tot++;
	e[tot].to=v;
	e[tot].next=first[u];
	first[u]=tot;
}

void dfs(int u,int fa){
	dp[u][0]=1;
   
   for (int p=first[u];p;p=e[p].next){
   	int v=e[p].to;
   	if (v==fa) continue;
   	dfs(v,u);
   	
   	Rep (j,k) ans+=dp[v][j]*dp[u][k-j-1];  
    For (j,k) dp[u][j]+=dp[v][j-1];
   	
   }
	
}


int main(){
	scanf("%d%d",&n,&k);
	For (i,n-1){
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	dfs(1,0);
	printf("%d",ans);
}

最后

以上就是斯文水壶最近收集整理的关于Codeforces 161 D Distance in Tree 树形DP的全部内容，更多相关Codeforces内容请搜索靠谱客的其他文章。