Submission #1127056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127056		underwaterkillerwhale	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	223 ms	37284 KiB

election_campaign

//#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define REB(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 1e5 + 7;
const int Mod = 1e9 + 7;///lon
const ll INF = 1e18 + 7;
const ll BASE = 137;
const int szBL = 450;

struct Fenwick_Tree {
    int m;
    int fen[N];

    void init (int n) {
        m = n;
    }

    void update (int pos, int val) {
        for (; pos <= m; pos += pos & -pos) fen[pos] += val;
    }
    int get (int pos) {
        int res = 0;
        for (; pos > 0; pos -= pos & -pos) res += fen[pos];
        return res;
    }
    int get (int L, int R) {
        assert(L <= R);
        return get(R) - get(L - 1);
    }
}BIT;

struct Data {
    int u, v, W;
};

int n, m;
vector<int> ke[N];
vector<Data> vec[N];

int par[N][25], pa[N], high[N], szC[N];
int Head[N], ein[N];

int dp[N], Tot[N];

void solution() {
    cin >> n;
    rep (i, 1, n - 1) {
        int u, v;
        cin >> u >> v;
        ke[u].pb(v);
        ke[v].pb(u);
    }
    function<void(int, int)> pdfs = [&] (int u, int p) {
        high[u] = high[p] + 1;
        par[u][0] = pa[u] = p;
        rep (i, 1, 20) par[u][i] = par[par[u][i - 1]][i - 1];
        szC[u] = 1;
        iter (&v, ke[u]) {
            if (v != p) {
                pdfs(v, u);
                szC[u] += szC[v];
            }
        }
    };
    pdfs(1, 0);
    auto LCA = [&] (int u, int v) {
        if (high[u] > high[v]) swap(u, v);
        rep (i, 0, 20)
            if (bit(high[v] - high[u], i)) v = par[v][i];
        if (u == v) return u;
        REB (i, 20, 0)
            if (par[v][i] != par[u][i]) {
                v = par[v][i], u = par[u][i];
            }
        return par[v][0];
    };
    function<void(int, int)> hld = [&] (int u, int p) {
        static int time_dfs = 0;
        ein[u] = ++time_dfs;
        Head[u] = p;

        int mxV = -1;
        iter (&v, ke[u]) {
            if (v != pa[u] && (mxV == -1 || szC[mxV] < szC[v])) mxV = v;
        }
        if (mxV != -1) hld(mxV, p);
        iter (&v, ke[u]) {
            if (v == pa[u] || v == mxV) continue;
            hld(v, v);
        }
    };
    hld(1, 1);
    cin >> m;
    rep (i, 1, m) {
        int u, v, w;
        cin >> u >> v >> w;
        int anc = LCA(u, v);
        vec[anc].pb({u, v, w});
    }
    BIT.init(n);
    auto Jump = [&] (int u, int anc) {
        int delta = high[u] - high[anc] - 1;
        assert(delta >= 0);
        rep (i, 0, 20) if (bit(delta, i)) u = par[u][i];
        return u;
    };
    auto Get = [&] (int anc, int u) -> int  {
        int res = 0;
        while (Head[u] != Head[anc]) {
            res += BIT.get(ein[Head[u]], ein[u]);
            u = pa[Head[u]];
        }
        res += BIT.get(ein[anc], ein[u]);
        return res;
    };
    function<void(int, int)> dfs = [&] (int u, int p) {
        iter (&v, ke[u]) {
            if (v != p) {
                dfs(v, u);
                Tot[u] += dp[v];
            }
        }
        dp[u] = Tot[u];
        iter (&id, vec[u]) {
            int k = id.u, t = id.v, W = id.W;
            if (high[k] > high[t]) swap(k, t);
            int curcost = 0;
            if (k == u) {
                curcost = Tot[u] - dp[Jump(t, u)] + Tot[t] + Get(u, t) + W;
            }
            else {
                curcost = Tot[u] - dp[Jump(k, u)] - dp[Jump(t, u)] + Tot[k] + Tot[t] + Get(u, k) + Get(u, t) + W;
            }
            dp[u] = max(dp[u], curcost);
        }
        iter (&v, ke[u]) {
            if (v != p) {
                int curVal = Tot[u] - dp[v];
                BIT.update(ein[v], curVal);
            }
        }
    };
    dfs(1, 0);
    cout << dp[1] <<"\n";
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +33
2 1
0 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