/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Wrong Answer 27ms 640.0 KiB
#3 Wrong Answer 25ms 532.0 KiB

Code

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

void solve() {
    int n;
    cin >> n;
    vector<ll> weight(n + 1);
    for(int i = 1; i <= n; i++) cin >> weight[i];
    vector<vector<pair<int, ll>>> g(n + 1);
    for(int i = 1; i < n; i++) {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    int root = 1;
    for(int i = 1; i <= n; i++) {
        if(g[i].size() == 1) {
            root = 1;
            break;
        }
    }

    ll ans = 0;
    vector<ll> dp(n + 1);

    auto dfs2 = [&](auto&& self, int u, int p, int l, ll mx) -> void {
        if(l >= 2) {
            ans = max(ans, mx + dp[u]);
            return;
        }
        mx += weight[u];
        for(auto &[v, w]: g[u]) {
            if(v == p) continue;
            self(self, v, u, l + 1, mx - (2 * w));
        }
        return;
    };

    auto dfs = [&](auto&& self, int u, int p) -> pair<ll, int> {
        if(g[u].size() == 1 && g[u][0].first == p) { // leaf
            dp[u] = weight[u];
            return {weight[u], 0};
        }
        priority_queue<ll> pq;
        ll mx = weight[u]; int cnt = 0;
        for(auto &[v, w]: g[u]) {
            if(v == p) continue;
            auto [x, cntV] = self(self, v, u);
            if(weight[u] <= (weight[u] - 2 * w) + x) {
                mx = (weight[u] - 2 * w) + x;
                cnt = cntV + 1;
            }
            pq.push((weight[u] - 2 * w) + x);
        }
        if(pq.size() >= 2) {
            ll x = pq.top(); pq.pop();
            x += pq.top() - weight[u];
            ans = max(ans, x);
        }
        if(cnt >= 2) ans = max(ans, mx);
        dp[u] = mx;
        dfs2(dfs2, u, p, 0, 0);
        return {mx, cnt};
    };
    dfs(dfs, root, 0);
    if(ans != LLONG_MAX) {
        cout << ans << endl;
        return;
    }
    assert(0);
    return;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc = 1;
    cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case " << t << ": ";
        solve();
    }
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1205 E. Make Cycle in Tree
Language
C++17 (G++ 13.2.0)
Submit At
2025-07-05 08:06:54
Judged At
2025-07-05 08:06:54
Judged By
Score
0
Total Time
27ms
Peak Memory
640.0 KiB