Submission #251893

#	Time	Username	Problem	Language	Result	Execution time	Memory
251893		LifeHappen__	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	252 ms	33400 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;

#define forinc(a, b, c) for(int a=b, _c=c; a<=_c; ++a)
#define fordec(a, b, c) for(int a=b, _c=c; a>=_c; --a)
#define forv(a, b) for(auto &a : b)
#define rep(i, n) forinc(i, 1, n)
#define repv(i, n) forinc(i, 0, n - 1)

#define ii pair<int,int>
#define fi first
#define se second
#define all(a) begin(a), end(a)
#define reset(f, x) memset(f, x, sizeof(f))
#define eb emplace_back
#define pb push_back

const int N = 1e5+5;
int n, m;
struct pack {int u, v, c;};
vector<pack> que[N];
vector<int> ad[N];
int st[N], en[N], id, it[4 * N];
int pd[N][26], dep[N], f[N], g[N];

void upd(int i, int val) {
    for(; i <= n; i += i & -i) it[i] += val;
}
int get(int i) {
    int ans = 0;
    for(; i; i -= i & -i) ans += it[i];
    return ans;
}

void dfs(int u, int par) {
    rep(i, 20) pd[u][i] = pd[pd[u][i - 1]][i - 1];
    st[u] = ++id;
    forv(v, ad[u]) if(v != par) {
        dep[v] = dep[u] + 1;
        pd[v][0] = u;
        dfs(v, u);
    }
    en[u] = id;
}
int lca(int u, int v) {
    if(dep[u] < dep[v]) swap(u, v);
    int unx = dep[u] - dep[v];
    fordec(i, 20, 0) if(unx >> i & 1) u = pd[u][i];
    if(u == v) return u;
    fordec(i, 20, 0) if(pd[u][i] != pd[v][i]) u = pd[u][i], v = pd[v][i];
    return pd[u][0];
}
void dfs1(int u, int par) {
    forv(v, ad[u]) if(v != par) {
        dfs1(v, u);
        g[u] += f[v];
    }
    forv(v, ad[u]) if(v != par) {
        upd(st[v], g[u] - f[v]);
        upd(en[v] + 1, f[v] - g[u]);
    }
    f[u] = g[u];
    forv(p, que[u]) {
        int x = p.u, y = p.v, c = p.c;
        f[u] = max(f[u], get(st[x]) + get(st[y]) + g[x] + g[y] - g[u] + c);
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    rep(i, n - 1) {
        int u, v;
        cin >> u >> v;
        ad[u].pb(v); ad[v].pb(u);
    }
    dfs(1, 0);
    cin >> m;
    rep(i, m) {
        int u, v, c;
        cin >> u >> v >> c;
        int p = lca(u, v);
        que[p].pb({u, v, c});
    }
    dfs1(1, 0);
    cout << f[1] << '\n';
}

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