Submission #1225573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225573		minhpk	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	134 ms	100760 KiB

election_campaign

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

int a;
vector<int> z[1000005];
int logarit[1000005];
int sta[1000005], fin[1000005], high[1000005];
int euler[2000005], st[2000005][21]; // cần gấp đôi kích thước euler
int tour;

struct node {
    int x, y, val;
};
node q[1000005];
vector<int> pos[1000005];

void dfs(int u, int par) {
    sta[u] = ++tour;
    euler[tour] = u;

    for (int v : z[u]) {
        if (v == par) continue;
        high[v] = high[u] + 1;
        dfs(v, u);
        euler[++tour] = u;
    }

    fin[u] = tour;
}

void build_log() {
    logarit[1] = 0;
    for (int i = 2; i <= 2 * a; i++) {
        logarit[i] = logarit[i / 2] + 1;
    }
}

void build_st() {
    for (int i = 1; i <= tour; i++) {
        st[i][0] = euler[i];
    }

    for (int j = 1; (1 << j) <= tour; j++) {
        for (int i = 1; i + (1 << j) - 1 <= tour; i++) {
            int u = st[i][j - 1];
            int v = st[i + (1 << (j - 1))][j - 1];
            st[i][j] = (high[u] < high[v] ? u : v);
        }
    }
}

int lca(int u, int v) {
    int l = sta[u], r = sta[v];
    if (l > r) swap(l, r);
    int j = logarit[r - l + 1];
    int u1 = st[l][j];
    int u2 = st[r - (1 << j) + 1][j];
    return (high[u1] < high[u2]) ? u1 : u2;
}


int bit[1000005];
void update(int i, int val) {
    i++;
    while (i <= tour) {
        bit[i] += val;
        i += i & -i;
    }
}

int query(int i) {
    i++;
    int res = 0;
    while (i > 0) {
        res += bit[i];
        i -= i & -i;
    }
    return res;
}

int dfs1(int u, int par) {
    int sum = 0;
    for (int v : z[u]) {
        if (v == par) continue;
        sum += dfs1(v, u);
    }

    int best = 0;
    for (int id : pos[u]) {
        auto [x, y, val] = q[id];
        int pre = val + query(sta[x]) + query(sta[y]);
        best = max(best, pre);
    }

    update(sta[u], -best);
    update(fin[u] + 1, best);

    return sum + best;
}

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

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

    dfs(1, 0);
    build_log();
    build_st();

    int c;
    cin >> c;
    for (int i = 1; i <= c; i++) {
        int x, y, val;
        cin >> x >> y >> val;
        int l = lca(x, y);
        pos[l].push_back(i);
        q[i] = {x, y, val};
    }

    cout << dfs1(1, 0) << "\n";

    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