Submission #853267

#	Time	Username	Problem	Language	Result	Execution time	Memory
853267		epicci23	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	173 ms	45092 KiB

election_campaign

#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n" 
#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()


const int N = 1e5 + 5;
const int LOG = 20;
vector<int> v[N];
int fw[N][2],tin[N],tout[N];
int lift[N][LOG];
int timer=0;
int dp[N],pre[N];
vector<array<int,3>> go[N];

void upd(int c,int t,int u){
  for(;c<N;c+=c&-c) fw[c][t]+=u;
}

int query(int c,int t,int res=0){
  for(;c;c-=c&-c) res+=fw[c][t];
  return res;
}

bool check(int a,int b){
 return tin[a]<=tin[b] && tin[b]<=tout[a];
}

int lca(int a,int b){
  if(check(a,b)) return a;
  for(int i=LOG-1;i>=0;i--) if(!check(lift[a][i],b)) a=lift[a][i];
  return lift[a][0];
}

void dfs(int c,int p){
  lift[c][0]=p;
  for(int i=1;i<LOG;i++) lift[c][i]=lift[lift[c][i-1]][i-1];
  tin[c]=++timer;
  tout[c]=tin[c];
  for(int x:v[c]){
  	if(x==p) continue;
  	dfs(x,c);
  	tout[c]=max(tout[c],tout[x]);
  }
}

void dfs2(int c,int p){
  for(int x:v[c]){
  	if(x==p) continue;
  	dfs2(x,c);
  	pre[c]+=dp[x];
  }
  dp[c]=max(dp[c],pre[c]);
  upd(tin[c],1,pre[c]),upd(tout[c]+1,1,-pre[c]);
  for(auto x:go[c]){
  	int cur=x[2];
  	cur+=query(tin[x[0]],1);
  	cur-=query(tin[x[0]],0);
  	cur+=query(tin[x[1]],1);
  	cur-=query(tin[x[1]],0);
  	cur-=pre[c];
  	dp[c]=max(dp[c],cur);
  }
  upd(tin[c],0,dp[c]),upd(tout[c]+1,0,-dp[c]);
}

void solve(){
  int n; cin >> n;
  for(int i=1;i<n;i++){
  	int a,b;
  	cin >> a >> b;
  	v[a].pb(b);
  	v[b].pb(a);
  }
  
  dfs(1,1);
  int q; cin >> q;

  array<int,3> ar[q+1];
  for(int i=1;i<=q;i++){
  	int a,b,c;
  	cin >> a >> b >> c;
    ar[i]={a,b,c};
    go[lca(a,b)].pb({a,b,c});
  }

  dfs2(1,1);

  cout << dp[1] << endl;
}

int32_t main(){

  cin.tie(0); ios::sync_with_stdio(0);
  
  int t=1;//cin >> t;
  while(t--) 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