【题目来源】
【题目描述】
A tree is a connected graph that doesn't contain any cycles.
The distance between two vertices of a tree is the length (in edges) of the shortest path between these vertices.
You are given a tree with n vertices and a positive number k. Find the number of distinct pairs of the vertices which have a distance of exactly k between them. Note that pairs (v, u) and (u, v) are considered to be the same pair.
题目大意：树是一个不包含任何圈的连通图。树的两个节点之间的距离是节点之间最短路径的长度（也就是边的长度）。给定一棵有 n 个节点的树和一个正整数 k，找出距离恰好为 k 的不同节点对的数量。注意，节点对 (v, u) 和节点对 (u, v) 被认为是相同的节点对。
【输入格式】
The first line contains two integers n and k (1 ≤ n ≤ 50000, 1 ≤ k ≤ 500) — the number of vertices and the required distance between the vertices.
Next n - 1 lines describe the edges as "ai bi" (without the quotes) (1 ≤ ai, bi ≤ n, ai ≠ bi), where ai and bi are the vertices connected by the i-th edge. All given edges are different.
【输出格式】
Print a single integer — the number of distinct pairs of the tree's vertices which have a distance of exactly k between them.
Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.
【输入样例一】
5 2
1 2
2 3
3 4
2 5
【输出样例一】
4
【输入样例二】
5 3
1 2
2 3
3 4
4 5
【输出样例二】
2
【数据范围】
1 ≤ n ≤ 50000, 1 ≤ k ≤ 500
【算法分析】
● 该算法通过一次 DFS 遍历，在每个节点处统计所有经过该节点的长度为 k 的路径，避免了枚举所有点对，显著提高了效率。
● f[u][j] 表示以 u 为根的子树中，距离 u 为 j 的节点数量。据此，f[u][0]=1 表示节点 u 到自身的距离为 0，计数为 1。
● 核心代码一
for(int j=0; j<k; j++) {ans+=f[u][j]*f[t][k-1-j];
}
核心代码一的功能是：当处理节点 u 时，计算经过节点 t 且长度为 k 的路径。
其中，f[u][j] 表示子树中距离 u 为 j 的节点数，f[t][k-1-j] 表示子树中距离 t 为 k-1-j 的节点数。两者相乘得到经过 u 且连接两棵子树的路径数。
● 核心代码二
for(int j=k; j>=1; j--) {f[u][j]+=f[t][j-1];
}核心代码二的功能是：将子节点 t 的信息合并到父节点 u，使用倒序更新避免重复计算。
【算法代码：链式前向星】
#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int N=5e4+5;
const int K=5e2+5;
int e[N<<1],ne[N<<1],h[N],idx;
LL f[N][K],ans;
int n,k;void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}void dfs(int u,int fa) {f[u][0]=1;for(int i=h[u]; i!=-1; i=ne[i]) {int t=e[i];if(t==fa) continue;dfs(t,u);for(int j=0; j<k; j++) {ans+=f[u][j]*f[t][k-1-j];}for(int j=k; j>=1; j--) {f[u][j]+=f[t][j-1];}}
}int main() {memset(h,-1,sizeof(h));cin>>n>>k;for(int i=1; i<n; i++) {int a,b;cin>>a>>b;add(a,b);add(b,a);}dfs(1,-1);cout<<ans<<endl;return 0;
}/*
in:
5 3
1 2
2 3
3 4
4 5out:
2
*/
【算法代码：邻接表】
#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int N=5e4+5;
const int K=5e2+5;
vector<int> v[N<<1];
LL f[N][K],ans;
int n,k;void dfs(int u,int fa) {f[u][0]=1;for(int i=0; i<v[u].size(); i++) {int t=v[u][i];if(t==fa) continue;dfs(t,u);for(int j=0; j<k; j++) {ans+=f[u][j]*f[t][k-1-j];}for(int j=k; j>=1; j--) {f[u][j]+=f[t][j-1];}}
}int main() {cin>>n>>k;for(int i=1; i<n; i++) {int a,b;cin>>a>>b;v[a].push_back(b);v[b].push_back(a);}dfs(1,-1);cout<<ans<<endl;return 0;
}/*
in:
5 3
1 2
2 3
3 4
4 5out:
2
*/
【参考文献】