제출 #527851

#제출 시각아이디문제언어결과실행 시간메모리
527851Koosha_mvElection Campaign (JOI15_election_campaign)C++14
100 / 100
425 ms64196 KiB
#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<pair<pair<int,int>,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){
	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){
	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];
		}
	}
	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 v : duo[u]){
		int sum=pd[v.F.F]+pd[v.F.S];
		maxm(dp[u],get(st[v.F.F])+get(st[v.F.S])-get(st[u])-get(st[u])-pd[u]+sum+v.S);
	}
}
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);
		if(lca==u){
			solo[u].pb({v,cost});
			continue ;
		}
		duo[lca].pb({{u,v},cost});
	}
	dfs2(1,1);
	cout<<dp[1];
}

컴파일 시 표준 에러 (stderr) 메시지

election_campaign.cpp:84:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   84 | main(){
      | ^~~~
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:96:11: warning: unused variable 'x' [-Wunused-variable]
   96 |   int u,v,x=0,y=0,cost;
      |           ^
election_campaign.cpp:96:15: warning: unused variable 'y' [-Wunused-variable]
   96 |   int u,v,x=0,y=0,cost;
      |               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...