제출 #1313984

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313984		chithanhnguyen	Election Campaign (JOI15_election_campaign)	C++20	10 / 100	279 ms	39216 KiB

election_campaign

/*
Author: Nguyen Chi Thanh - High School for the Gifted - VNU.HCM (i2528)
*/
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ull unsigned long long
#define ld long double
#define pii pair<int, int>
#define fi first
#define se second
#define __builtin_popcount __builtin_popcountll
#define all(x) (x).begin(), (x).end()
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(x) ((1ll << (x)))

#define debug(a, l, r) for (int _i = (l); _i <= (r); ++_i) cout << (a)[_i] << ' '; cout << '\n';

struct Query {
    int u, v, c;
};

const int MAXN = 1e5 + 5;
const int INF  = 1e18 + 5;
const int LG   = 17;
int n, m;
vector<int> adj[MAXN];
vector<Query> queries[MAXN];

// LCA Implementation
int depth[MAXN], up[LG + 1][MAXN];

void dfsLCA(int u, int par = 0) {
    up[0][u] = par;

    for (int j = 1; j <= LG; ++j)
        up[j][u] = up[j - 1][up[j - 1][u]];
    
    for (int v : adj[u]) {
        if (v == par) continue;
        depth[v] = depth[u] + 1;
        dfsLCA(v, u);
    }
}

int lift(int u, int k) {
    for (int j = 0; j <= LG; ++j)
        if (BIT(k, j)) u = up[j][u];
    return u;
}

int lca(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    int diff = depth[v] - depth[u];
    v = lift(v, diff);

    if (u == v) return u;

    for (int j = LG; j >= 0; --j) {
        if (up[j][u] != up[j][v]) {
            u = up[j][u];
            v = up[j][v];
        }
    }

    return up[0][u];
}
// End of LCA Implementation

void init() {
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfsLCA(1);

    cin >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v, c; cin >> u >> v >> c;
        int at = lca(u, v);
        queries[at].push_back({u, v, c});
    }
}

// Main algorithm (DP on Tree)
int dp[2][MAXN];
/*
    dp[used][u]: maximum value when consider subtree rooted at u
    used = 0: not choose u
    used = 1: choose u
*/

vector<int> checkset;
void dfs(int u, int par = 0) {
    // Computing dp[0][u]
    dp[0][u] = 0;
    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);
        dp[0][u] += max(dp[0][v], dp[1][v]);
    }

    // Computing dp[1][u]
    for (auto &qry : queries[u]) {
        checkset.clear();
        int a = qry.u, b = qry.v;

        int val = dp[0][u];
        if (a != u) {
            val += dp[0][a];
            checkset.push_back(lift(a, depth[a] - depth[u] - 1));
        }
        if (b != u) {
            val += dp[0][b];
            checkset.push_back(lift(b, depth[b] - depth[u] - 1));
        }

        for (auto v : checkset)
            val -= max(dp[0][v], dp[1][v]);
        
        
        dp[1][u] = max(dp[1][u], val + qry.c);
    }
}

void solve() {
    for (int i = 1; i <= n; ++i)
        dp[0][i] = dp[1][i] = -INF;
    dfs(1);

    cout << max(dp[0][1], dp[1][1]);
}

signed main() {
    #ifdef NCTHANH
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    init();
    solve();

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 0 / 30
• Subtask 5: 0 / 10
• Subtask 6: 0 / 40