Submission #1257352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257352		King87arshia	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	363 ms	36080 KiB

election_campaign

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

const int N = 1e5 + 5;

#define int long long

int n, q;
int par[N], big[N], sz[N], head[N], st[N], seg[N << 2], lazy[N << 2], _time, a[N], h[N], dp[N], dp2[N], ft[N];
vector<int> adj[N], dis[N];

struct node {
    int u, v, c;
};
vector<node> vec[N];

void dfs_sz(int u = 0, int p = -1) {
    sz[u] = 1;
    big[u] = -1;
    for (int v : adj[u]) { 
        if (v == p)
            continue;
        par[v] = u;
        h[v] = h[u] + 1;
        dfs_sz(v, u);
        sz[u] += sz[v];
        if (big[u] == -1 || sz[v] > sz[big[u]])
            big[u] = v;
    }
}

void dfs(int u = 0, int p = -1) {
    st[u] = _time++;
    if (big[u] != -1) {
        head[big[u]] = head[u];
        dfs(big[u], u);
    }
    for (int v : adj[u]) {
        if (v == p || v == big[u]) 
            continue;
        head[v] = v;
        dfs(v, u);
    }
    ft[u] = _time;
}

void shift(int id, int st, int en) {
    lazy[id << 1] += lazy[id];
    lazy[id << 1 | 1] += lazy[id];
    int mid = st + en >> 1;
    seg[id << 1] += (mid - st) * lazy[id];
    seg[id << 1 | 1] += (en - st) * lazy[id];
    lazy[id] = 0;
}

void update(int l, int r, long long x, int id = 1, int st = 0, int en = n) {
    if (r <= st || en <= l)
        return;
    if (l <= st && en <= r) {
        seg[id] += (en - st) * x;
        lazy[id] += x;
        return;
    }
    shift(id, st, en);
    int mid = st + en >> 1;
    update(l, r, x, id << 1, st, mid);
    update(l, r, x, id << 1 | 1, mid, en);
    seg[id] = seg[id << 1] + seg[id << 1 | 1];
}
 
long long get(int l, int r, int id = 1, int st = 0, int en = n) {
    if (r <= st || en <= l)
        return 0;
    if (l <= st && en <= r)
        return seg[id];
    shift(id, st, en);
    int mid = st + en >> 1;
    return get(l, r, id << 1, st, mid) + get(l, r, id << 1 | 1, mid, en);
}

void update_hld(int u, int v, long long x) {
    while (true) {
        if (head[u] == head[v]) {
            if (st[u] > st[v])
                swap(u, v);
            update(st[u], st[v] + 1, x);
            break;
        }
        if (st[head[u]] > st[head[v]])
            swap(u, v);
        update(st[head[u]], st[u] + 1, x);
        u = par[head[u]];
    }
}
 
long long get_hld(int u, int v) {
    long long ans = 0;
    while (true) {
        if (head[u] == head[v]) {
            if (st[u] > st[v])
                swap(u, v);
            ans += get(st[u], st[v] + 1);
            break;
        }
        if (h[head[u]] < h[head[v]])
            swap(u, v);
        ans += get(st[head[u]], st[u] + 1);
        u = par[head[u]];
    }
    return ans;
}

int lca(int u, int v) {
    while (head[u] != head[v]) {
        if (h[head[u]] > h[head[v]]) 
            swap(u, v);
        v = par[head[v]];
    }
    return (h[u] < h[v] ?u: v);
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs_sz();
    dfs();
    cin >> q;
    while (q--) {
        int u, v, c;
        cin >> u >> v >> c;
        --u; --v;
        vec[lca(u, v)].push_back({u, v, c});
    }
    for (int u = 0; u < n; u++)
        dis[h[u]].push_back(u);
    for (int d = n - 1; d >= 0; d--) {
        for (int u : dis[d]) {
            dp[u] = dp2[u];
            for (auto x : vec[u]) {
                int A = x.u, B = x.v, C = x.c;
                if (st[A] > st[B]) 
                    swap(A, B);
                if (ft[A] > ft[B])
                    dp[u] = max(dp[u], dp2[B] + C + get_hld(u, B));
                else
                    dp[u] = max(dp[u], dp2[A] + dp2[B] + C + get_hld(B, A) - dp2[u]);
            }
            if (u != 0) 
                dp2[par[u]] += dp[u];
        }
        for (int u : dis[d]) {
            if (u == 0) 
                continue;
            update_hld(u, u, dp2[par[u]] - dp[u]);
        }
    }
    cout << dp[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