Submission #527848

#	Time	Username	Problem	Language	Result	Execution time	Memory
527848		Koosha_mv	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	472 ms	65664 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#define int ll

const int N=4e5+99,lg=20;

int n,m,cnt=1,st[N],ft[N],h[N],a[N],dp[N],pd[N],par[lg][N],fenwik[N];
vector<int> emp,g[N];
vector<pair<int,int>> solo[N];
vector<vector<int>> duo[N];

void add(int x,int val){
	for(x++;x<N;x+=x&-x) fenwik[x]+=val;
}
void add(int l,int r,int val){
	//cout<<l<<" "<<r<<" : "<<val<<endl;
	add(l,val);
	add(r,-val);
}
int get(int x){
	int res=0;
	for(x++;x>0;x-=x&-x) res+=fenwik[x];
	return res;
}
int LCA(int u,int v,int &x,int &y){
	f_(l,lg-1,0){
		if(h[u]<=h[par[l][v]]){
			v=par[l][v];
		}
	}
	if(u==v) return u;
	f_(l,lg-1,0){
		if(par[l][u]!=par[l][v]){
			u=par[l][u],v=par[l][v];
		}
	}
	x=u,y=v;
	return par[0][u];
}
void dfs1(int u,int p){
	par[0][u]=p; f(l,1,lg) par[l][u]=par[l-1][par[l-1][u]];
	st[u]=cnt++;
	for(auto v : g[u]){
		if(v==p) continue ;
		h[v]=h[u]+1;
		dfs1(v,u);
	}
	ft[u]=cnt;
}
void dfs2(int u,int p){
	for(auto v : g[u]){
		if(v==p) continue ;
		dfs2(v,u);
		dp[u]+=dp[v];
		pd[u]+=dp[v];
		add(st[u]+1,ft[u],dp[v]);
		add(st[v],ft[v],-dp[v]);
	}
	for(auto v : solo[u]){
		maxm(dp[u],get(st[v.F])+pd[v.F]+v.S-get(st[u]));
	}
	for(auto vec : duo[u]){
		int sum=pd[vec[0]]+pd[vec[1]];
		maxm(dp[u],get(st[vec[0]])+get(st[vec[1]])-pd[u]+vec[4]+sum-2*get(st[u]));
		/*if(dp[u]==29){
			dbgv(vec);
			eror(get(st[vec[0]])-get(st[u]));
			eror(get(st[vec[1]])-get(st[u]));
			exit(0);
		}*/
	}
	//cout<<u<<" -> "<<dp[u]<<endl;
}
main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	cin>>n;
	f(i,1,n){
		int u,v;
		cin>>u>>v;
		g[u].pb(v);
		g[v].pb(u);
	}
	dfs1(1,1);
	cin>>m;
	f(i,0,m){
		int u,v,x=0,y=0,cost;
		cin>>u>>v>>cost;
		if(h[u]>h[v]) swap(u,v);
		int lca=LCA(u,v,x,y);
		//cout<<u<<" "<<v<<" -> "<<lca<<" "<<x<<" "<<y<<endl;
		if(lca==u){
			solo[u].pb({v,cost});
			continue ;
		}
		duo[lca].pb(emp);
		duo[lca].back().pb(u);
		duo[lca].back().pb(v);
		duo[lca].back().pb(x);
		duo[lca].back().pb(y);
		duo[lca].back().pb(cost);
	}
	dfs2(1,1);
	cout<<dp[1];
}

Compilation message (stderr)

election_campaign.cpp:93:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   93 | main(){
      | ^~~~

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