Submission #1296384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296384		Gray	Election Campaign (JOI15_election_campaign)	C++20	10 / 100	136 ms	48276 KiB

election_campaign

// #pragma GCC optimize("Ofast,unroll-loops")
#include <algorithm>
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define mp make_pair
#define ff first
#define ss second
#define ln "\n"
using namespace std;
const ll INF = 2e18;
const ll MOD = 1e9+7;


ll n, m;
vector<vector<ll>> A;
vector<array<ll, 3>> r;
vector<vector<ll>> bin, check;
vector<ll> level, tin, tout, dp;

void generatetr(ll u, ll p, ll clev, ll &timer){
    tin[u]=timer; timer++;
    bin[u][0]=p; level[u]=clev;
    for (ll i=1; i<20; i++) bin[u][i]=bin[bin[u][i-1]][i-1];
    for (auto v:A[u]){
        if(v==p) continue;
        generatetr(v, u, clev+1, timer);
    }
    tout[u]=timer-1;
}
ll lca(ll u, ll v){
    if (level[u]<level[v]) swap(u, v);
    ll cl = level[u]-level[v];
    for (ll i=0; i<20; i++) if ((1<<i)&cl) u=bin[u][i];
    if (u==v) return u;
    for (ll i=19; i>=0; i--){
        if (bin[u][i]!=bin[v][i]) {
            u=bin[u][i]; v=bin[v][i];
        }
    }
    return bin[u][0];
}
pair<ll, ll> plca(ll u, ll v){
    if (level[u]<level[v]) swap(u, v);
    ll cl = level[u]-level[v]-1;
    for (ll i=0; i<20; i++) if ((1<<i)&cl) u=bin[u][i];
    if (bin[u][0]==v) return {u, v};
    u=bin[u][0];
    for (ll i=19; i>=0; i--){
        if (bin[u][i]!=bin[v][i]) {
            u=bin[u][i]; v=bin[v][i];
        }
    }
    return {u, v};
}

struct Fenwick{
    vector<ll> tr;
    ll n, off;
    Fenwick(ll N){
        off=10; n=N+20; tr.resize(n+1);
    }
    void add(ll i, ll x){
        i+=off; for (; i<=n; i+=(-i&i)) tr[i]+=x;
    }
    ll get(ll i){
        i+=off; ll res=0;
        for (; i; i-=(-i&i)) res+=tr[i];
        return res;
    }
};

void dfs(ll u, ll p, Fenwick &tr){
    ll sum=0;
    for (auto v:A[u]){
        if (v==p) continue;
        dfs(v, u, tr);
        sum+=dp[v];
    }
    ll best=sum;
    for (auto i:check[u]){
        pair<ll, ll> cons = plca(r[i][0], r[i][1]);
        // cout << i << " - " << r[i][2] << " - " << r[i][0] << " w " << r[i][1] << " : " << cons.ff << " & " << cons.ss << " calc: " << tr.get(r[i][0]) << " - " << tr.get(r[i][1]) << " - " << sum-dp[cons.ff]-dp[cons.ss]+r[i][2] << ln;
        best=max(best, tr.get(tin[r[i][0]])+tr.get(tin[r[i][1]])+sum-dp[cons.ff]-dp[cons.ss]+r[i][2]);
    }
    dp[u]=best;
    // cout << u << ": " << best << ln;
    for (auto v:A[u]){
        if (v==p) continue;
        tr.add(tin[v], sum-dp[v]);
        tr.add(tout[v]+1, -sum+dp[v]);
    }
    tr.add(tin[u], sum);
    tr.add(tin[u]+1, -sum);
}

void solve(){
    cin >> n; A.resize(n+1);
    tin.resize(n+1); tout.resize(n+1);
    check.resize(n+1); dp.resize(n+1);
    level.resize(n+1); bin.resize(n+1, vector<ll>(20));
    for (ll i=0; i<n-1; i++){
        ll u, v; cin >> u >> v;
        A[u].push_back(v);
        A[v].push_back(u);
    }
    ll timer=0;
    generatetr(1, 1, 1, timer);
    cin >> m; r.resize(m);
    for (ll i=0; i<m; i++){
        cin >> r[i][0] >> r[i][1] >> r[i][2];
        ll lc = lca(r[i][0], r[i][1]);
        check[lc].push_back(i);
    }
    Fenwick tr(n);
    dfs(1, 1, tr);
    cout << dp[1] << ln;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll t=1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

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