Submission #1368920

#TimeUsernameProblemLanguageResultExecution timeMemory
1368920tranvinhhuy2010Election Campaign (JOI15_election_campaign)C++20
100 / 100
108 ms29972 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int nmax = 1e5 + 5, lg = 17;
int n, m, d[nmax], up[nmax][20], in[nmax], out[nmax], timer;
vector <int> g[nmax];
vector <tuple <int, int, ll>> path[nmax];
ll bit[nmax], dp[nmax], sum[nmax];

void dfs(int u) {
    in[u] = ++timer;

    for (int v : g[u]) {
        if (v==up[u][0]) continue;

        d[v] = d[u] + 1;
        up[v][0] = u;
        for (int j=1; j<=lg; j++)
            up[v][j] = up[up[v][j - 1]][j - 1];

        dfs(v);
    }

    out[u] = timer;
}

int lca(int u, int v) {
    if (d[u]<d[v]) swap(u, v);
    int dif = d[u] - d[v];
    for (int j=0; j<=lg; j++)
        if (dif >> j & 1)
            u = up[u][j];

    if (u==v) return u;

    for (int j=lg; j>=0; j--)
        if (up[u][j]!=up[v][j]) u = up[u][j], v = up[v][j];

    return up[u][0];
}

void update(int i, ll x) {
    while (i<=n) {
        bit[i] += x;
        i += i & -i;
    }
}

void update_range(int l, int r, ll x) {
    update(l, x);
    update(r + 1, -x);
}

ll get(int i) {
    ll s = 0;
    while (i>0) {
        s += bit[i];
        i -= i & -i;
    }

    return s;
}

void dfs_dp(int u) {
    for (int v : g[u]) {
        if (v==up[u][0]) continue;
        dfs_dp(v);
        sum[u] += dp[v];
    }

    dp[u] = sum[u];

    for (auto [a, b, c] : path[u]) {
        ll val = c + sum[u];
        if (a!=u) val += get(in[a]);
        if (b!=u) val += get(in[b]);
        dp[u] = max(dp[u], val);
    }

    update_range(in[u], out[u], sum[u] - dp[u]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

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

    dfs(1);

    cin >> m;

    while (m--) {
        int a, b; ll c;
        cin >> a >> b >> c;
        path[lca(a, b)].push_back({a, b, c});
    }

    dfs_dp(1);

    cout << dp[1];

    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...