Submission #347784

#	Time	Username	Problem	Language	Result	Execution time	Memory
347784		Blerargh	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	423 ms	42604 KiB

election_campaign

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

typedef long long ll;
#define _ <<" "<<
const ll MAXN = 1e5+5;
const ll INF = 1e18;

vector<ll> adjlist[MAXN];
bool visited[MAXN];

//lca 
ll parent[18][MAXN], depth[MAXN];
ll n;

//hld
ll stsize[MAXN], preorder[MAXN], head[MAXN], id;

void hld_sz(ll u, ll par){
    stsize[u] = 1;
    for (auto &v : adjlist[u]){
        if (v != par) {
            hld_sz(v, u);
            stsize[u] += stsize[v];

            if (adjlist[u][0] == par || stsize[v] > stsize[adjlist[u][0]]) swap(v, adjlist[u][0]);
        }
    }
    return;
}

void hld(ll u, ll par){
    preorder[u] = ++id;
    if (u == par) head[u] = u;
    for (auto v : adjlist[u]){
        if (v != par){
            head[v] = (v == adjlist[u][0]) ? head[u] : v;
            hld(v, u);
        }
    }
    return;
}

void dfs(ll u, ll par, ll dep){
    visited[u] = 1;
    depth[u] = dep;
    parent[0][u] = par;
    for (auto v : adjlist[u]){
        if (!visited[v]) dfs(v, u, dep+1);
    }
    return;
}

void lcainit(){
    for (int power=1; power<18; power++) for (int i=1; i<=n; i++){
        parent[power][i] = parent[power-1][parent[power-1][i]];
    }
    return;
}

ll lca(ll a, ll b){
    if (depth[a] > depth[b]) swap(a,b);

    ll diff = depth[b] - depth[a];
    ll power = 0;
    while (diff){
        if (diff%2) b = parent[power][b];

        diff>>=1;
        power++;
    }

    if (a == b) return a;

    for (int i=17; i>=0; i--){
        if (parent[i][a] != parent[i][b]){
            a = parent[i][a];
            b = parent[i][b];
        }
    }
    return parent[0][a];
}

ll nodesum[MAXN], childsum[MAXN];

void upd(ll x, ll val, ll type){
    if (type) {
        for (int i=x; i<=n; i+=i&(-i)) nodesum[i] += val;
    } else {
        for (int i=x; i<=n; i+=i&(-i)) childsum[i] += val;
    }
    return;
}

ll query(ll a, ll b, ll type){
    ll resa=0, resb=0;
    if (type) {
        for (int i=--a; i; i-=i&(-i)) resa += nodesum[i];
        for (int i=b; i; i-=i&(-i)) resb += nodesum[i];
    } else {
        for (int i=--a; i; i-=i&(-i)) resa += childsum[i];
        for (int i=b; i; i-=i&(-i)) resb += childsum[i];
    }
    return resb-resa;
}

ll dp[MAXN];
bool visitd[MAXN];
vector<tuple<ll,ll,ll> > lcas[MAXN];

void solve(ll u){
    visitd[u] = 1;
    for (auto v : adjlist[u]){
        if (visitd[v]) continue;
        solve(v);
        dp[u] += dp[v];
    }

    for (auto paths : lcas[u]){
        ll x, y, val;
        ll nsum = 0, csum = 0;
        tie(x, y, val) = paths;
        // cout << x _ y _ val << "gay ";

        while (true){
            if (head[x] == head[y]){
                if (preorder[x] > preorder[y]) swap(x, y);
                nsum += query(preorder[x], preorder[y], 1);
                csum += query(preorder[x], preorder[y], 0);
                break;
            } else {
                if (depth[head[x]] >= depth[head[y]]) {
                    nsum += query(preorder[head[x]], preorder[x], 1);
                    csum += query(preorder[head[x]], preorder[x], 0);
                    x = parent[0][head[x]];
                } else {
                    nsum += query(preorder[head[y]], preorder[y], 1);
                    csum += query(preorder[head[y]], preorder[y], 0);
                    y = parent[0][head[y]];
                }
            }
        }

        // cout << csum _ nsum _ val << "vals ";

        ll newval = csum - nsum + val;
        dp[u] = max(dp[u], newval);
    }

    upd(preorder[u], dp[u], 1);
    upd(preorder[parent[0][u]], dp[u], 0);

    // cout << u _ dp[u] << '\n';
    return;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i=1; i<n; i++){
        ll a, b;
        cin >> a >> b;
        adjlist[a].push_back(b);
        adjlist[b].push_back(a);
    }

    dfs(1,1,0);
    lcainit();

    hld_sz(1,1);
    hld(1,1);

    ll q;
    cin >> q;

    while (q--) {
        ll a, b, c;
        cin >> a >> b >> c;
        lcas[lca(a,b)].emplace_back(a,b,c);
    }

    solve(1);
    cout << dp[1];

    // for (int i=1; i<11; i++) cout << stsize[i] _ preorder[i] _ head[i] << '\n';
    // cout << lca(2, 7) _ lca(3, 5) _ lca(1, 1) _ lca(6, 7);
}

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