1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
struct Highway {
    int u, v;
    long long int len;
    long long int wei;
};
int N, M;
vector<Highway> ways;
vector<unordered_map<int, int>> links;
void getWeight(int from, int root) { //gather weight from branches
    long long int sumWeight = 1;
    for (auto branch = links[from].begin(); branch != links[from].end(); ++branch) {
        if (branch->first != root) {
            getWeight(branch->first, from);
            sumWeight += ways[links[branch->first][from]].wei;
        }
    }
    ways[links[from][root]].wei = sumWeight;
}
int main() {
    cin >> N >> M;
    links.resize(N + 1); ways.resize(N);
    int u, v, k;
    for (int i = 1; i<N; ++i) {
        cin >> u >> v >> k;
        links[u][v] = links[v][u] = i;
        ways[i] = {u, v, k, 1};
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX