Submission #405151

#	Time	Username	Problem	Language	Result	Execution time	Memory
405151		timmyfeng	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	276 ms	27356 KiB

election_campaign

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

const int N = 100001, L = __lg(N) + 1;

vector<array<int, 3>> updates[N];
int par[L][N], in[N], out[N], t;
vector<int> adj[N];

int votes[N], fenw[N], n;

void update(int a, int x) {
    for ( ; a <= n; a += a & -a) {
        fenw[a] += x;
    }
}

int query(int a) {
    int sum = 0;
    for ( ; a > 0; a -= a & -a) {
        sum += fenw[a];
    }
    return sum;
}

void dfs_init(int u) {
    in[u] = ++t;
    for (auto c : adj[u]) {
        if (c != par[0][u]) {
            par[0][c] = u;
            dfs_init(c);
        }
    }
    out[u] = t;
}

void dfs_solve(int u) {
    for (auto c : adj[u]) {
        if (c != par[0][u]) {
            dfs_solve(c);
        }
    }

    for (auto c : adj[u]) {
        if (c != par[0][u]) {
            update(in[u], votes[c]);
            update(out[u] + 1, -votes[c]);

            update(in[c], -votes[c]);
            update(out[c] + 1, votes[c]);
        }
    }

    votes[u] = query(in[u]);
    for (auto [x, y, w] : updates[u]) {
        votes[u] = max(votes[u], query(in[x]) + query(in[y]) - query(in[u]) + w);
    }
}

bool ancestor(int u, int v) {
    return in[u] <= in[v] && out[v] <= out[u];
}

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

    cin >> n;

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

    dfs_init(1);
    out[0] = t;
    cerr << "\n";

    for (int i = 1; i <= __lg(n); ++i) {
        for (int j = 1; j <= n; ++j) {
            par[i][j] = par[i - 1][par[i - 1][j]];
        }
    }

    int m;
    cin >> m;

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;

        int p = u;
        if (!ancestor(p, v)) {
            for (int j = __lg(n); j >= 0; --j) {
                if (!ancestor(par[j][p], v)) {
                    p = par[j][p];
                }
            }
            p = par[0][p];
        }

        updates[p].push_back({u, v, w});
    }

    dfs_solve(1);

    cout << votes[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