Coding_Practice/codeforce/1399E1.cpp at master · BWbwchen/Coding_Practice · GitHub

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#define DEBUG
#include <bits/stdc++.h>
#define ll unsigned long long int
#define MAXN 10e16 + 1

using namespace std;


class problem {
    private :
        // pair {to_id, edge_id}
        vector<vector<pair<int, int>> > graph;
        vector<bool > visited;
        vector<ll > cnt;
        set<pair<ll, int> > st;
        vector<ll > w;
        int n;
        ll s;
        ll answer;

        void dfs (int start, int upEdge = -1) {
            // calculate the leaf node of this edge
            // if leaf => cnt = 1
            // for each neighbor
            //      dfs
            //      cnt[me] += cnt[neighbor]

            if (visited[start]) return ;
            bool isLeaf = true;
            visited[start] = true;

            for (auto [to, i] : graph[start]) {
                if (!visited[to]) {
                    isLeaf = false;
                    dfs(to, i) ;
                    if (upEdge != -1) cnt[upEdge] += cnt[i];
                }
            }
            if (isLeaf) cnt[upEdge] = 1;
        }
        void init () {
            graph.resize(n);
            visited.resize(n, false);
            cnt.resize(n, 0);
            w.resize(n, 0);
        }
        ll diff (int id) {
            return cnt[id] * w[id] - cnt[id] * (w[id]/2);
        }
        ll get_sum () {
            ll _s = 0;
            for (int i = 0; i < n-1; ++i) {
                // prevent sort every loop
                st.insert({diff(i), i});
                _s += cnt[i] * w[i];
            }
            return _s;
        }
    public :
        problem () {
            n = 0;
            s = 0;
            answer = 0;
            graph.clear();
            visited.clear();
            cnt.clear();
            st.clear();
            w.clear();
        }
        void input () {
            cin >> n >> s;
            init();

            int u, v;
            ll weight;
            for (int i = 0; i < n-1; ++i) {
                cin >> u >> v >> weight;
                u--; v--;
                while (weight > s) {
                    weight /= 2;
                    ++answer;
                }

                graph[u].push_back({v, i});
                graph[v].push_back({u, i});
                w[i] = weight;
            }
        }
        void solve () {
            dfs(0);
            ll sum = get_sum();

            while (sum > s) {
                auto id = st.rbegin()->second;
                sum -= diff(id);
                w[id] /= 2;
                st.erase(prev(st.end()));
                st.insert({diff(id), id});
                ++answer;
            }
            cout << answer << endl;
        }
};


int main () {
    #ifdef DEBUG
    freopen("in.in", "r", stdin);
    #endif

    int n_case;
    cin >> n_case;
    while (n_case--) {
        problem t;
        t.input();
        t.solve();
    }
    return 0;
}