Submission #891281

#	Time	Username	Problem	Language	Result	Execution time	Memory
891281		viwlesxq	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	236 ms	43600 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S &a, const T &b) {
    return a > b && (a = b) == b;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
    return a < b && (a = b) == b;
}
const int inf = 1e9 + 7;
const int INF = 1e18 + 7;
const int mod = 998244353;
const int N = 1e5 + 1;

struct Fenwick {
    int n;
    vector<int> t;
    void build(int n) {
        this->n = n;
        t.assign(n + 1, 0);
    }

    void upd(int i, int x) {
        for (; i <= n; i += i & -i) {
            t[i] += x;
        }
    }

    int sum(int i) {
        int res = 0;
        for (; i > 0; i -= i & -i) {
            res += t[i];
        }
        return res;
    } int get(int l, int r) {
        return sum(r) - sum(l - 1);
    }
};

int position, timer, up[N][17];
vector<int> g[N], sub(N), heavy(N), head(N), pos(N), dp(N), tin(N), tout(N), depth(N);
vector<array<int, 3>> path[N];
vector<Fenwick> t(2);

void dfs(int v, int p) {
    tin[v] = ++timer;
    sub[v] = 1;
    up[v][0] = p;
    for (int i = 1; i < 17; ++i) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for (int to : g[v]) {
        if (to != p) {
            depth[to] = depth[v] + 1;
            dfs(to, v);
            sub[v] += sub[to];
        }
    }
    for (int to : g[v]) {
        if (to != p && sub[to] * 2 >= sub[v]) {
            heavy[v] = to;
        }
    }
    tout[v] = ++timer;
}

void decompose(int v, int p, int h) {
    head[v] = h;
    pos[v] = ++position;
    if (heavy[v]) {
        decompose(heavy[v], v, h);
    }
    for (int to : g[v]) {
        if (to != p && to != heavy[v]) {
            decompose(to, v, to);
        }
    }
}

bool upper(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v) {
    if (upper(u, v)) {
        return u;
    }
    if (upper(v, u)) {
        return v;
    }
    for (int i = 16; i >= 0; --i) {
        if (!upper(up[u][i], v)) {
            u = up[u][i];
        }
    }
    return up[u][0];
}

int count(int a, int b, int i) {
    int res = 0;
    while (head[a] != head[b]) {
        if (depth[b] > depth[a]) {
            swap(a, b);
        }
        res += t[i].get(pos[head[a]], pos[a]);
        a = up[head[a]][0];
    }
    if (depth[b] > depth[a]) {
        swap(a, b);
    }
    res += t[i].get(pos[b], pos[a]);
    return res;
}

void count_dp(int v, int p) {
    int sum = 0;
    for (int to : g[v]) {
        if (to != p) {
            count_dp(to, v);
            sum += dp[to];
        }
    }
    dp[v] = sum;
    for (auto [a, b, c] : path[v]) {
        chmax(dp[v], count(a, b, 0) - count(a, b, 1) + sum + c);
    }
    t[0].upd(pos[v], sum);
    t[1].upd(pos[v], dp[v]);
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    t[0].build(n), t[1].build(n);
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1, 1);
    decompose(1, -1, 1);
    int m;
    cin >> m;
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        path[lca(a, b)].push_back({a, b, c});
    }
    count_dp(1, 1);
    cout << dp[1];
}

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