题目链接：
codeforces 161D
题目大意：
给出一棵树，每条边的边权是1，问两点之间的路径长度为k的点对有多少个？
题目分析：就是因为父亲已经被维护过，所以现在dp[p][j-1]表示p点到所有点中长度为k的点的个数，再减去那些存在于当前子树中的点，然后就是非u的子树中的点到u的距离为j的点的个数，最后枚举每个点，统计他们，，因为每条符合要求的路径算了两次，所以最后结果要除以2。 AC代码：;LL;int n,k,a,b;LL dp[MAX][507],ans;vector<int> e[MAX];void add ( int u , int v ){e[u].push_back ( v );e[v].push_back ( u );}void Clear ( ){for ( int i = 0 ; i < MAX ; i++ )e[i].clear();}void dfs ( int u , int p ){dp[u][0] = 1;for ( int i = 1 ; i <= k ; i++ )dp[u][i] = 0;for ( int i = 0 ; i < e[u].size() ; i++ ){int v = e[u][i];if ( v == p ) continue;dfs ( v , u );for ( int j = 1 ; j <= k ; j++ )dp[u][j] += dp[v][j-1];}}void solve ( int u , int p ){for ( int i = 0 ; i < e[u].size() ; i++ ){int v = e[u][i];if ( v == p ) continue;for ( int j = k; j >= 1 ; j– ){dp[v][j] += dp[u][j-1];if ( j > 1 ) dp[v][j] -= dp[v][j-2];}solve ( v , u );}}int main ( ){while ( ~scanf ( “%d%d” , &n , &k ) ){Clear();for ( int i = 1 ; i < n ; i++ ){scanf ( “%d%d” , &a , &b );add ( a , b );}ans = 0;dfs ( 1 , -1 );solve ( 1 , -1 );/*for ( int i = 1; i <= n ; i++ )for ( int j = 0 ; j <= k ; j++ )cout << i << ” ” << j << ” ” << dp[i][j] << endl;*/for ( int i = 1 ; i <= n ; i++ )ans += dp[i][k];printf ( “%I64d\n” , ans/2LL );}}
不是每个人都一定快乐，不是每种痛都一定要述说。
