80142 - 2026挑战赛提高组46·50
统计题目(材料题)
统计树上路径 给出一棵n（$1 \leq n \leq 10^4$ ）个节点的，每条边有边权的树。求有多少组点对 $(i,j)$，满足这两个点之间的树上简单路径长度是k（$1 \leq k \leq 100$ ）的整数倍。其中 $(i,j)$和 $(j,i) , i = \not j$视为两组不同的点对。
试补全程序：
|
#include<iostream> #include<vector> using namespace std;
int n, k; struct edge { int to; int val; }; vector<edge> map[10001]; int d[10001][100]; long long total;
void dfs(int node, int fa) { ① for (edge e : map[node]) if (e.to != fa) { dfs( ② ); for (int a = 0; a < k; a++) { ③ } for (int a = 0; a < k; a++) { ④ } } } int main() { cin >> n >> k; for (int i = 1; i < n; i++) { int x, y, w; cin >> x >> y >> w; map[x].push_back({ y,w }); map[y].push_back({ x,w }); } dfs(1, 0); ⑤ cout << total; return 0; } |
关注我们
