#650653 (C++17) No.1488 Max Score of the Tree

• 問題: No.1488 Max Score of the Tree
• ユーザー: tokusakurai
• 提出日時: 2021-04-23 21:36:40
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 23 ms / 2,000 ms
• コード長: 2,283 bytes
• コンパイル時間: 3,942 ms
• コンパイル使用メモリ: 203,936 KB
• 最終ジャッジ日時: 2025-01-20 23:40:11
• ジャッジサーバーID （参考情報）: judge1 / judge4

ファイルパターン	結果
sample	AC * 3
other	AC * 29

ソースコード

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define each(e, v) for(auto &e: v)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const int MOD = 1000000007;
//const int MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};
struct io_setup{
    io_setup(){
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout << fixed << setprecision(15);
    }
} io_setup;
template<typename T, bool directed = false>
struct Weighted_Graph{
    struct edge{
        int to; T cost; int id;
        edge(int to, T cost, int id) : to(to), cost(cost), id(id) {}
    };
    vector<vector<edge>> es;
    const T INF_T;
    const int n;
    int m;
    Weighted_Graph(int n) : es(n), INF_T(numeric_limits<T>::max()/2), n(n), m(0) {}
    void add_edge(int from, int to, T cost){
        es[from].emplace_back(to, cost, m);
        if(!directed) es[to].emplace_back(from, cost, m);
        m++;
    }
    vector<pii> ps;
    T S = 0;
    int dfs(int now, int pre = -1){
        int s = (sz(es[now]) == 1? 1 : 0);
        each(e, es[now]){
            if(e.to == pre) continue;
            int k = dfs(e.to, now);
            s += k, ps.eb(e.cost, k), S += e.cost*k;
        }
        return s;
    }
    void solve(int K){
        dfs(0);
        vector<ll> dp(K+1, 0);
        each(e, ps){
            rep3(i, K, 0){
                if(i+e.first <= K){
                    chmax(dp[i+e.first], dp[i]+e.first*e.second);
                }
            }
        }
        cout << S+dp[K] << '\n';
    }
};
int main(){
    int N, K; cin >> N >> K;
    Weighted_Graph<ll> G(N);
    rep(i, N-1){
        int u, v, c; cin >> u >> v >> c; u--, v--;
        G.add_edge(u, v, c);
    }
    G.solve(K);
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX