Submission #1266772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266772		MPG	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	452 ms	113324 KiB

election_campaign

//#pragma GCC optomize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
//#pragma GCC target("sse,sse2,sse4.1,sse4.2") 
//#pragma GCC target("avx2")



#include <bits/stdc++.h>
using namespace std;
typedef long long       ll;
//#define     max_heap priority_queue<ll>
#define     max_heap priority_queue<pair <ll, ll>>
#define     min_heap priority_queue<pair <ll, ll>, vector<pair <ll, ll>>, greater<pair <ll, ll>>>
//#define     min_heap priority_queue< pair <ll, pair <ll, ll> >, vector< pair <ll, pair <ll, ll> > >, greater< pair <ll, pair <ll, ll> > > >
//#define     min_heap priority_queue< pair <pair <ll, ll>, pair<ll, ll>>, vector< pair <pair <ll, ll>, pair<ll,ll>> >, greater< pair <pair <ll, ll>, pair<ll, ll>> > >


#define     sariE cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define     filE freopen("in.txt", "r", stdin), freopen("out1.txt", "w", stdout); 
#define     endl '\n'
#define     md(a) (a % mod + mod) % mod
#define     pb push_back
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//cout << setprecision(5) << fixed << f;
//hash prime = 769


ll const maxn = 1e5 + 123;
ll const inf = 2e15;
ll const loG = 23;
ll const mod = 1e9 + 7;
//ll const mod = 998244353;
ll const sq = 380;
ll power(ll a, ll b, ll mod){if(b==0)return 1;if(b==1)return a;ll x = power(a, b / 2, mod);return (((x * x) % mod) * (b % 2 ? a : 1)) % mod;}





ll n, par[loG][maxn], jam[loG][maxn], h[maxn], st[maxn], fn[maxn], tim, zir[maxn], dp[maxn];
vector <ll> g[maxn];
vector <pair <ll, ll>> upd[maxn];
vector <pair <pair <ll, ll>, ll>> qu[maxn];

void pre_dfs(ll v, ll p){
    st[v] = ++tim;
    h[v] = h[p] + 1;
    par[0][v] = p;
    for (ll u : g[v]){
        if (u != p)
            pre_dfs(u, v);
    }
    fn[v] = ++tim;
}


ll jump(ll v, ll h){
    for (int i = loG - 1; i > -1; i--){
        if (h & (1 << i)){
            v = par[i][v];
        }
    }
    return v;
}

bool ispar(ll v, ll u){
    return (st[v] <= st[u]) && (fn[v] >= fn[u]);
}


ll lca(ll v, ll u){
    if (h[v] > h[u])
        swap(v, u);
    u = jump(u, h[u] - h[v]);
    if (u == v)
        return v;
    for (int i = loG - 1; i > -1; i--){
        if (par[i][v] != par[i][u]){
            u = par[i][u];
            v = par[i][v];
        }
    }
    return par[0][v];
}

ll get(ll v, ll u){
    ll ret = zir[u] - dp[u];
    ll now = u;
    for (int i = loG - 1; i > -1; i--){
        if (ispar(v, par[i][now])){
            ret += jam[i][now];
            now = par[i][now];
        }
    }
    return ret;
}


void dfs(ll v, ll p){
    ll sum = 0;
    for (ll u : g[v]){
        if (u != p){
            dfs(u, v);
            sum += dp[u];
        }
    }
    dp[v] = sum;
    zir[v] = sum;
    for (auto p : qu[v]){
        ll a = p.first.first, b = p.first.second, c = p.second;
        //cout << v << " " << a << ' ' << b << endl;
        ll ret = sum + c;
        if (a != v){
            ll bach = jump(a, h[a] - h[v] - 1);
            ret += get(bach, a);
        }
        if (b != v){
            ll bach = jump(b, h[b] - h[v] - 1);
            ret += get(bach, b);
        }
        dp[v] = max(dp[v], ret);
    }
    for (auto p : upd[v]){
        ll i = p.first, now = p.second;
        ll val = zir[v] - dp[v];
        if (i == 0)
            jam[i][now] = val;
        else
            jam[i][now] = jam[i - 1][now] + jam[i - 1][par[i - 1][now]];
    }

    //cout << v << ' ' << dp[v] << endl;

}



void Solve(){

cin >> n;
for (int i = 1; i < n; i++){
    ll a, b; cin >> a >> b;
    g[a].pb(b);
    g[b].pb(a);
}
pre_dfs(1, 1);
for (int i = 1; i < loG; i++){
    for (int v = 1; v < n + 1; v++){
        par[i][v] = par[i - 1][par[i - 1][v]];
    }
}
for (int i = 1; i < n + 1; i++){
    for (int j = 0; j < loG; j++){
        ll p = par[j][i];
        upd[p].pb({j, i});
    }
}
ll q; cin >> q;
while (q--){
    ll a, b, c; cin >> a >> b >> c;
    ll lc = lca(a, b);
    //cout << a << ' ' << b << " lca is " << lc << endl;
    qu[lc].pb({{a, b}, c});
}
for (int i = 1; i < n + 1; i++)
    sort(upd[i].begin(), upd[i].end());
dfs(1, 1);
cout << dp[1] << endl;




}






int main(){
sariE;
//filE;



int test = 1;
//cin >> test;
while (test--) Solve();
return 0;
}

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