Submission #967580

#	Time	Username	Problem	Language	Result	Execution time	Memory
967580		AlperenT_	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	179 ms	83956 KiB

election_campaign

#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define ld long double
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cout <<#x << " : " << x << "\n" ;
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e6+10 + 10,  inf = 1e9+10 , lg = 19 , mod = 1000696969 ;
int fen[maxn][2] , sm[maxn] , dp[maxn] , par[maxn][lg+1] , n ,st[maxn] , en[maxn] , c= 1 , dis[maxn] ;
vector <int> G[maxn] ;
vector <pair<pii,int> > Q[maxn];
int up(int v ,int d){
    rep(i , 0 ,lg){
        if(d>>i&1) v = par[v][i] ;
    }
    return v ;
}
int lca(int v ,int u){
    if(dis[v] < dis[u])swap(v, u);
    v = up(v ,dis[v]-dis[u]);
    per(i , lg, 0){
        if(par[v][i] != par[u][i]){
            v = par[v][i] ;
            u = par[u][i] ;
        }
    }
    if(v==u)return v ;
    return par[v][0] ;
}
void upd(int x, int w , int t){
    while(x <= n){
        fen[x][t] += w ;
        x += x&-x ;
    }
}
int que(int x , int t){
    int ans = 0;
    while(x){
        ans = (fen[x][t] +ans);
        x -= x&-x ;
    }
    return ans ;
}
void bui(int v , int p =0){
    par[v][0] = p ;
    rep(i ,1 ,lg){
        par[v][i] = par[par[v][i-1]][i-1] ;
    }
    st[v] = c; c++;
    for(int u : G[v]){
        if(u == p)continue ;
        dis[u] = dis[v]+1;
        bui(u,v);
    }
    en[v] = c-1 ;
}
void dfs(int v ,int p =0){
    for(int u : G[v]){
        if(u == p)continue ;
        dfs(u , v);
        sm[v] += dp[u] ;
    }
    dp[v] = sm[v]; 
    for(auto x :Q[v]){
        int a= x.F.F , b = x.F.S , w = x.S ;
        int ans = que(st[a] , 0) + que(st[b] , 0) - que(st[a] , 1) - que(st[b] ,1) + sm[v] + w;
        dp[v] = max(dp[v] , ans) ;  
    }
    upd(st[v] , sm[v] , 0) ;upd(en[v]+1, -sm[v], 0) ;
    upd(st[v] , dp[v] , 1);upd(en[v]+1 ,-dp[v] , 1);
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    cin >> n ;
    rep(i , 1, n-1){
        int v, u ;
        cin >> v >> u ;
        G[v].pb(u);
        G[u].pb(v);
    }
    bui(1);
    int q;
    cin >> q ;
    while(q--){
        int v, u , w ;
        cin >> v >> u >> w ;
        Q[lca(v,u)].pb({{v,u},w});
    }
    dfs(1);
    cout << dp[1] << "\n"; 
    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