Submission #482904

#	Time	Username	Problem	Language	Result	Execution time	Memory
482904		K4YAN	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	317 ms	43872 KiB

election_campaign

//Be Name Khoda

#include<bits/stdc++.h>
#pragma GCC optimize ("Ofast,unroll-loops")
#pragma GCC target ("avx2")

using namespace std;

#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define piii pair<pii, int>
#define piiii pair<pii, pii>
#define piiiii pair<pii, piii>
#define pll pair<ll, ll>
#define plll pair<pll, ll>

const ll mxn = 1e5 + 16;
ll n, k, m, q, w;
ll dp[mxn][2], par[mxn][17], hch[mxn], chn[mxn], lbl[mxn], dis[mxn], subt[mxn];
vector<int> adj[mxn];
vector<plll> g[mxn];
bool mark[mxn];
plll p;

void DFS(int v) {
    mark[v] = 1;
    subt[v] = 1, dis[v] = w++;
    for(auto u : adj[v]) {
        if(!mark[u]) {
            par[u][0] = v, DFS(u);
            subt[v] += subt[u];
            if(subt[hch[v]] < subt[u]) hch[v] = u;
        }
    }w--;
}
void SAGZAN(int v) {
    lbl[v] = w++;
    if(chn[v] == -1) chn[v] = v;
    if(hch[v] != -1) {
        chn[hch[v]] = chn[v];
        SAGZAN(hch[v]);
    }
    for(auto u : adj[v]) {
        if(u == par[v][0] || u == hch[v]) continue;
        SAGZAN(u);
    }
}
ll find_jad(int v, int u) {
    if(dis[v] > dis[u]) {
        swap(v, u);
    }
    for(int i = 16; i > -1; i--) {
        if(dis[u] - (1 << i) < dis[v]) continue;
        u = par[u][i];
    }
    if(u == v) return v;
    for(int i = 16; i > -1; i--) {
        if(par[v][i] == par[u][i]) continue;
        v = par[v][i], u = par[u][i];
    }
    v = par[v][0];
    return v;
}
struct segtree {

    int s = 1;
    vector<int> v;
    void init(ll n) {
        while(s < n) s <<= 1;
        v.assign(2 * s, 0);
    }
    void add(int i, ll k, int x, int lx, int rx) {
        if(rx - lx == 1) {
            v[x] = k;
            return;
        }
        int m = (lx + rx) >> 1;
        if(i < m) add(i, k, 2 * x + 1, lx, m);
        else add(i, k, 2 * x + 2, m, rx);
        v[x] = v[2 * x + 1] + v[2 * x + 2];
    }
    void add(int i, ll k) {
        add(i, k, 0, 0, s);
    }
    ll cal(int l, int r, int x, int lx, int rx) {
        if(rx <= l || r <= lx) return 0;
        if(l <= lx && rx <= r) return v[x];
        int m = (lx + rx) >> 1;
        ll ans1 = cal(l, r, 2 * x + 1, lx, m);
        ll ans2 = cal(l, r, 2 * x + 2, m, rx);
        return ans1 + ans2;
    }
    ll cal(int l, int r) {
        return cal(l, r, 0, 0, s);
    }

};
segtree st;

ll cal(int v, int u, int l) {
    ll r = v, res = 0, t;
    while(r > 1) {
        t = chn[r];
        if(dis[l] >= dis[t]) {
            res = res + st.cal(lbl[r] - dis[r] + dis[l] + 1, lbl[r] + 1);
            break;
        }
        res = res + st.cal(lbl[chn[r]], lbl[r] + 1);
        r = par[chn[r]][0];
    }r = u;
    while(r > 1) {
        t = chn[r];
        if(dis[l] >= dis[t]) {
            res = res + st.cal(lbl[r] - dis[r] + dis[l] + 1, lbl[r] + 1);
            break;
        }
        res = res + st.cal(lbl[chn[r]], lbl[r] + 1);
        r = par[chn[r]][0];
    }
    res += dp[l][1];
    return res;
}

void SAGZAN_Solve(int v) {

    for(auto u : adj[v]) {
        if(u == par[v][0]) continue;
        SAGZAN_Solve(u);
        dp[v][1] += dp[u][0];
    }
    for(auto u : g[v]) {
        dp[v][0] = max(dp[v][0], u.second + cal(u.first.first, u.first.second, v));
    }
    dp[v][0] = max(dp[v][1], dp[v][0]);
    st.add(lbl[v], dp[v][1] - dp[v][0]);

}

void input() {

    fill(hch, hch + mxn, -1), fill(chn, chn + mxn, -1);
    cin >> n;
    for(int i = 1; i < n; i++) {
        int v, u;
        cin >> v >> u;
        adj[v].push_back(u), adj[u].push_back(v);
    }DFS(1), SAGZAN(1);
    for(int j = 1; j < 17; j++) {
        for(int i = 1; i <= n; i++) {
            par[i][j] = par[par[i][j - 1]][j - 1];
        }
    }
    cin >> m;
    for(int i = 0; i < m; i++) {
        int v, u, c, w;
        cin >> v >> u >> c;
        w = find_jad(v, u);
        g[w].push_back({{v, u}, c});
    }

}

void solve() {

    st.init(n);
    SAGZAN_Solve(1);
    cout << dp[1][0] << endl;

}

int main() {

    ios::sync_with_stdio(false); cin.tie(NULL);

    input(), solve();

    return 0;

}
/*
20
17 10
11 4
8 3
3 16
1 14
15 18
5 4
6 18
10 18
19 4
16 7
2 13
4 12
12 20
9 20
18 13
20 14
14 7
13 7
15
19 9 2341
13 8 6974
8 3 3339
15 17 6515
10 13 4370
1 7 8376
18 2 9272
6 7 4595
1 20 505
10 9 308
6 19 8937
2 15 5072
5 4 4217
2 4 4170
19 12 8204
*/

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