codeforces 161D Distance in Tree (树形DP 经典题)
题意:给你一颗树,和一个数k,问树中长度为k的路径的条数.分析:一看就是树形DP的类型.树形DP的特点就是用所有叶子节点的信息更新出其父亲节点,然后这些父亲节点再作为叶子节点,这样层层递归直到根节点. 这里很容易想到的一种叶子节点更新父亲节点的方式如下: 定义dp[i][j]dp[i][j]为节点i为根的所有子树中长度为j的路径的条数. 那么就容易有:dp[i][j]=∑u(u为i的所有