Submission #1168512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168512		aycnl	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	118 ms	26956 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;

#define ii pair <int, int>
#define ff first
#define ss second
#define bit(i) (1 << (i))

#define fto(i, a, b) for (int i = (a); i <= (b); ++i)
#define fdto(i, a, b) for (int i = (a); i >= (b); --i)
#define flto(i, a, b) for (int i = (a); (1 << i) <= (b); ++i)

#define pb push_back
#define pf push_front

#define endl "\n"
#define oo (int)(1e9 + 7)
#define maxN 100005

#define l(s) s.length()

#define vi vector <int>
#define vii vector <ii>

#define fat(x, y) for (auto x : y)
#define fit(x, y) for (int x : y)
#define fiit(x, y) for (ii x : y)

#define EPS 1e-9
#define pi (acos(-1))
#define ll long long

int n, m, tme;
vi ke[maxN];
vector<pair<int, ii>> path[maxN];
int sta[maxN], fin[maxN], h[maxN];
int par[20][maxN];
ll bt[maxN], dp[maxN];

void ud(int i, ll x) {
    for (; i <= n; i += (i& -i)) bt[i] += x;
}

ll qry(int i) {
    ll res = 0;
    for (; i; i -= (i & -i)) res += bt[i];
    return res;
}

void pre_dfs(int u) {
    flto(j, 1, h[u]) par[j][u] = par[j-1][par[j-1][u]];
    sta[u] = ++tme;
    for (int v : ke[u]) if (v != par[0][u]) {
        par[0][v] = u;
        h[v] = h[u] + 1;
        pre_dfs(v);
    }
    fin[u] = tme;
}

int lca(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    fdto(i, 17, 0) if (h[u] - bit(i) >= h[v]) u = par[i][u];
    if (u == v) return u;
    fdto(i, 17, 0) if (par[i][u] != par[i][v]) u = par[i][u], v = par[i][v];
    return par[0][u];
}

void dfs(int u) {
    ll sum = 0;
    for (int v : ke[u]) if (v != par[0][u]) {
        dfs(v);
        sum += dp[v];
    }
    dp[u] = sum;
    for (auto tmp : path[u]) {
        auto [x, y] = tmp.ss;
        dp[u] = max(dp[u], qry(sta[x]) + qry(sta[y]) + tmp.ff + sum);
    }

    ud(sta[u], sum - dp[u]);
    ud(fin[u] + 1, dp[u] - sum);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    fto(i, 1, n-1) {
        int u, v; cin >> u >> v;
        ke[u].pb(v);
        ke[v].pb(u);
    }
    pre_dfs(1);
    cin >> m;
    fto(i, 1, m) {
        int u, v, c; cin >> u >> v >> c;
        path[lca(u, v)].pb({c, {u, v}});
    }
    dfs(1);
    cout << dp[1] << endl;

    return 0;
}

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