Submission #1314148

#TimeUsernameProblemLanguageResultExecution timeMemory
1314148chithanhnguyenElection Campaign (JOI15_election_campaign)C++20
100 / 100
145 ms36844 KiB
/*
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/Euler Tour Implementation
int depth[MAXN], up[LG + 1][MAXN];
int st[MAXN], en[MAXN], timer = 0;

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

    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);
    }

    en[u] = timer;
}

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/Euler Tour Implementation

// Data Structures
struct FenwickTree {
    int n;
    vector<int> fen;

    FenwickTree() {}
    FenwickTree(int _n) : n(_n), fen(n + 5, 0) {}

    void update(int idx, int v) {
        for (int i = idx; i <= n; i += i & -i)
            fen[i] += v;
    }

    int get(int idx) {
        int sum = 0;
        for (int i = idx; i; i -= i & -i)
            sum += fen[i];
        return sum;
    }

    void updateRange(int l, int r, int v) {
        update(l, v);
        update(r + 1, -v);
    }
};
// End of Data Structures

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
*/
FenwickTree fen;

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]) {
        int a = qry.u, b = qry.v;

        int val = dp[0][u];
        if (a != u) {
            // int p = lift(a, depth[a] - depth[u] - 1);
            val += fen.get(st[a]);
            // val -= max(dp[0][p], dp[1][p]);
        }
        if (b != u) {
            // int p = lift(b, depth[b] - depth[u] - 1);
            val += fen.get(st[b]);
            // val -= max(dp[0][p], dp[1][p]);
        }
        
        dp[1][u] = max(dp[1][u], val + qry.c);
    }

    fen.updateRange(st[u], en[u], dp[0][u] - max(dp[0][u], dp[1][u]));
}

void solve() {
    fen = FenwickTree(n);
    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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...