神勇草莓

文章
6
资源
0
加入时间
2年10月24天

codeforces 161D D. Distance in Tree(树形dp)

题目链接:codeforces 161D题目大意:给出一棵树,每条边的边权是1,问两点之间的路径长度为k的点对有多少个?题目分析:定义状态dp[i][k]代表以i为根的子树中的点到达点i的长度为k的点的个数。定义V为与u相邻的点的集合,p是u的父亲然后转移方程很简单:dp[u][j]=∑v∈Vdp[v][j−1]dp[u][j]= \sum_{v \in V}dp[v][j-1]然后我们利用处