Submission #890617

#	Time	Username	Problem	Language	Result	Execution time	Memory
890617		iskhakkutbilim	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	221 ms	51764 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

const int N = 1e5 + 1;

struct Fenw{
    vector <int> fenw;
    int n;
    Fenw(int n = 0) : fenw(n + 1, 0), n(n) {}
    void upd(int i, int val){
        for (; i <= n; i += i & -i ){
            fenw[i] += val;
        }
    }
    int get(int i){
        int cnt = 0;
        for (; i > 0; i -= i & -i ){
            cnt += fenw[i];
        }
        return cnt;
    }
    int get(int l, int r){
        return get(r) - get(l - 1);
    }
} Sub, Dp;

vector <int> G[N];

int up[N][21], d[N], h[N], sub[N];

void dfs(int u, int p){
    up[u][0] = p;
    for ( int i = 1; i <= 20; i++ ){
        up[u][i] = up[up[u][i - 1]][i - 1];
    }
    sub[u] = 1;
    for ( auto &v: G[u] ){
        if ( v != p ){
            d[v] = d[u] + 1;
            dfs(v, u);
            sub[u] += sub[v];
        }
    }
    for ( auto &v: G[u] ){
        if ( v != p ){
            if ( h[u] == -1 or sub[h[u]] < sub[v] ){
                h[u] = v;
            }
        }
    }
}

int lca(int u, int v){
    if ( d[u] < d[v] ) swap(u, v);
    int dif = d[u] - d[v];
    for ( int i = 0; i <= 20; i++ ){
        if ( dif >> i & 1 ){
            u = up[u][i];
        }
    }
    if ( u == v ){
        return u;
    }
    for ( int i = 20; i >= 0; i-- ){
        if ( up[u][i] != up[v][i] ){
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}

int chain[N], top[N], id[N], ct = 0, rt = 1;

void hld(int u, int p){
    id[u] = ++ct;
    chain[u] = rt;
    if ( top[rt] == -1 ){
        top[rt] = u;
    }
    if ( h[u] != -1 ) hld(h[u], u);
    for ( auto &v: G[u] ){
        if ( v != p and h[u] != v ){
            ++rt; hld(v, u);
        }
    }
}

int query(int u, int v){
    if ( d[u] < d[v] ){
        return 0;
    }
    // v must be Parent of u
    int ans = 0;
    while ( chain[u] != chain[v] ){
        int nxt = top[chain[u]];
        ans += Sub.get(id[nxt], id[u]) - Dp.get(id[nxt], id[u]);
        u = up[nxt][0];
    }
    ans += Sub.get(id[v], id[u]) - Dp.get(id[v], id[u]);
    return ans;
}

int sb[N], dp[N];

vector <int> qu[N], A(N), B(N), C(N);

void dfs2(int u, int p){
    int q = 0;
    for ( auto &v: G[u] ){
        if ( v != p ){
            dfs2(v, u);
            q += dp[v];
        }
    }
    sb[u] = q;
    for ( auto &i: qu[u] ){
        int cnt = query(A[i], u) + query(B[i], u) + C[i] + sb[u];
        chmax(dp[u], cnt);
    }
    chmax(dp[u], sb[u]);
    Sub.upd(id[u], sb[u]);
    Dp.upd(id[u], dp[u]);
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(h, -1, sizeof(h));
    memset(top, -1, sizeof(top));
    dp[0] = -1;

    int n; cin >> n;
    Sub = Dp = Fenw(n);
    for ( int i = 1; i < n; i++ ){
        int u, v; cin >> u >> v;
        G[u].pb(v), G[v].pb(u);
    }
    dfs(1, 0); hld(1, 0);
    int m; cin >> m;
    for ( int i = 0; i < m; i++ ){
        cin >> A[i] >> B[i] >> C[i];
        qu[lca(A[i], B[i])].pb(i);
    }
    dfs2(1, 0);
    cout << dp[1];

    cout << '\n';
}

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