/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 540.0 KiB
#2 Accepted 2ms 540.0 KiB
#3 Accepted 2ms 540.0 KiB
#4 Accepted 1ms 540.0 KiB
#5 Accepted 1ms 540.0 KiB
#6 Accepted 1ms 772.0 KiB
#7 Accepted 1ms 328.0 KiB
#8 Accepted 1ms 540.0 KiB
#9 Accepted 1ms 540.0 KiB
#10 Accepted 1ms 540.0 KiB
#11 Accepted 2ms 560.0 KiB
#12 Accepted 89ms 39.137 MiB
#13 Accepted 207ms 121.68 MiB
#14 Accepted 235ms 133.918 MiB
#15 Accepted 219ms 143.094 MiB
#16 Accepted 146ms 85.02 MiB
#17 Accepted 125ms 69.773 MiB
#18 Accepted 109ms 54.27 MiB
#19 Accepted 157ms 100.355 MiB
#20 Accepted 103ms 48.27 MiB
#21 Accepted 97ms 42.188 MiB
#22 Accepted 117ms 66.438 MiB
#23 Accepted 122ms 69.535 MiB
#24 Accepted 154ms 97.188 MiB
#25 Accepted 166ms 106.273 MiB
#26 Accepted 70ms 23.68 MiB
#27 Accepted 209ms 170.578 MiB
#28 Accepted 72ms 26.812 MiB
#29 Accepted 95ms 45.066 MiB
#30 Accepted 152ms 115.375 MiB
#31 Accepted 189ms 152.191 MiB
#32 Accepted 528ms 488.52 MiB
#33 Accepted 379ms 335.688 MiB
#34 Accepted 127ms 72.859 MiB
#35 Accepted 136ms 87.852 MiB
#36 Accepted 99ms 51.27 MiB
#37 Accepted 77ms 35.938 MiB
#38 Accepted 138ms 88.062 MiB
#39 Accepted 71ms 29.938 MiB
#40 Accepted 108ms 66.52 MiB
#41 Accepted 122ms 69.535 MiB
#42 Accepted 264ms 219.523 MiB
#43 Accepted 197ms 158.273 MiB
#44 Accepted 185ms 136.77 MiB
#45 Accepted 226ms 173.688 MiB
#46 Accepted 121ms 75.688 MiB
#47 Accepted 300ms 259.312 MiB
#48 Accepted 201ms 152.258 MiB
#49 Accepted 82ms 39.02 MiB
#50 Accepted 448ms 461.02 MiB

Code

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    vector<vector<int>> g(n + 1);
    for(int i = 0; i + 1 < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>> (2, vector<ll> (k + 1, 0))); // [vertex][left / right][length]
    auto dfs = [&](auto&& self, int u, int par) -> ll {
        dp[u][0][1] = dp[u][1][1] = a[u];
        short dir = 0;
        ll mx = 0;
        for(auto &v: g[u]) {
            if(v == par) continue;
            mx = max(mx, self(self, v, u));
            for(int i = 2; i <= k; i++) {
                if(dp[v][1][i - 1] == 0 && dp[v][0][i - 1] == 0) break;
                dp[u][dir][i] = a[u] + max(dp[v][0][i - 1], dp[v][1][i - 1]);
            }
            ++dir;
        }
        for(int i = 1; i <= k; i++) {
            if(dp[u][0][i] && dp[u][1][k - i + 1]) {
                mx = max(mx, dp[u][0][i] + dp[u][1][k - i + 1] - a[u]);
            }
            if(dp[u][1][i] && dp[u][0][k - i + 1]) {
                mx = max(mx, dp[u][1][i] + dp[u][0][k - i + 1] - a[u]);
            }
        }
        return mx;
    };
    cout << dfs(dfs, 1, 0) << endl;
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1160 Max path sum (Easy Version)
Language
C++17 (G++ 13.2.0)
Submit At
2025-03-24 18:17:37
Judged At
2025-03-24 18:17:37
Judged By
Score
100
Total Time
528ms
Peak Memory
488.52 MiB