題目鏈接
題解：
首先，我們需要考慮一下整個是一顆樹，輸入的是起點到終點，還有起點到終點的危險值，算出固定長度下所有路的風險值的總和。
所以直接遍歷這棵樹，遍歷每一個點，1到N，用深搜，一段路長度達到 k 就結束，不夠也要結束，為了防止重複，還得開一個布爾數組，防止走回頭路，走過的要進行標記已走過，沒有走過的要標記未走過。
然後，我們要考慮用什麼來存儲樹的節點，一般存子節點和父節點，我們會採用vector<int>e[N]，用序號表示父節點，值來表示子節點，這樣子不斷去遍歷
但是，這個題目還需要存儲危險值，所以我們可以用結構體直接存儲這三個值，或者用向量結構體去存儲（具體看代碼）
最後，注意數據範圍，首先看n的範圍到了5000，單個危險值的範圍到達10的6次方，危險值的總和範圍會超過了Int的範圍，所以最後算總和的變量要開範圍到long long.
代碼如下：
#include <bits/stdc++.h>
using namespace std;
int n, k, x, y, z;
long long allsum = 0;
const int N = 1e6;
struct Node {
int end;
int wei;
//終點節點，危險值
};
vector<Node>tree[N];
//開始節點
//不能走回頭路，所以需要標記是否走過
bool vis[N];
void dfs(int deep, int sum, int length) {
if (length == k) {
//到特地的長度，就可以返回了
//也可以加
// sum+=tree[deep].wei;
allsum += sum;
return;
}
//如果還沒到長度
//遍歷該節點的子節點
for (auto &t : tree[deep]) {
//如果走過的路就跳過
if (vis[t.end]) {
continue;
}
// sum += t.wei;
vis[t.end] = 1;
dfs(t.end, sum + t.wei, length + 1);
vis[t.end] = 0;
}
return;
}
int main() {
cin >> n >> k;
for (int i = 2; i <= n; i++) {
cin >> x >> y >> z;
//因為需要反過來經過道路也可以正向經過道路
//道路沒有箭頭
tree[x].push_back({y, z});
tree[y].push_back({x, z});
//所以需要雙向存儲，存儲兩次開頭和終點
}
for (int i = 1; i <= n; i++) {
vis[i] = 1;
dfs(i, 0, 0);
vis[i] = 0;
}
cout << allsum ;
return 0;
}
本文章為轉載內容，我們尊重原作者對文章享有的著作權。如有內容錯誤或侵權問題，歡迎原作者聯繫我們進行內容更正或刪除文章。
