Submission #289900

#	Time	Username	Problem	Language	Result	Execution time	Memory
289900		YJU	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	607 ms	27540 KiB

election_campaign

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll MOD=1e9+7;
const ll N=1e5+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<62);
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()

//input
ll n,m,x,y,c;
vector<ll> v[N],lis;
//tree
ll height[N],depth[N],sz[N],top[N],to[N],ti,fa[N],dg[N];
vector<pair<ll,pll> > q[N];
//segment tree
ll seg[4*N];
//dp
ll dp[N];
queue<ll> que;

void PDFS(ll nd,ll pa){
	sz[nd]=1;
	depth[nd]=depth[fa[nd]=pa]+1;
	for(ll i:v[nd]){
		if(i==pa)continue;
		PDFS(i,nd);
		height[nd]=max(height[nd],height[i]+1);
		sz[nd]+=sz[i];
	}
}

void DFS(ll nd,ll pa){
	ll id=-1;
	to[nd]=ti++;
	for(ll i:v[nd]){
		if(i==pa)continue;
		id=(id==-1?i:(sz[id]<sz[i]?i:id));
	}
	if(id==-1)return ;
	top[id]=top[nd];
	DFS(id,nd);
	for(ll i:v[nd]){
		if(i==pa||i==id)continue;
		top[i]=i;
		DFS(i,nd);
	}
}

ll lca(ll nda,ll ndb){
	while(top[nda]!=top[ndb]){
		if(depth[top[nda]]<depth[top[ndb]])swap(nda,ndb);
		nda=fa[top[nda]];
	}
	return (depth[nda]<depth[ndb]?nda:ndb);
}

ll sum(ll id,ll l,ll r,ll ql,ll qr){
	if(l>=ql&&r<=qr)return seg[id];
	if(l>=qr||r<=ql)return 0;
	ll mid=(l+r)/2;
	return sum(id*2,l,mid,ql,qr)+sum(id*2+1,mid,r,ql,qr);
}

void ins(ll id,ll l,ll r,ll t,ll d){
	if(l==r-1){seg[id]+=d;return;}
	ll mid=(l+r)/2;
	if(t<mid){ins(id*2,l,mid,t,d);}else{ins(id*2+1,mid,r,t,d);}
	seg[id]=seg[id*2]+seg[id*2+1];
}

ll Q(ll nda,ll ndb){
	ll res=0;
	while(top[ndb]!=top[nda]){
		res+=sum(1,0,n,to[top[ndb]],to[ndb]+1);
		ndb=fa[top[ndb]];
	}
	return res+sum(1,0,n,to[nda],to[ndb]+1);
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	depth[0]=-1;top[1]=1;
	cin>>n;
	REP(i,n-1)cin>>x>>y,v[x].pb(y),v[y].pb(x);
	PDFS(1,0);
	DFS(1,0);
	cin>>m;
	REP(i,m){
		cin>>x>>y>>c;
		q[lca(x,y)].pb(mp(c,mp(x,y)));
	}
	REP1(i,n){
		dg[i]=SZ(v[i]);
		if(dg[i]==1&&i!=1)que.push(i);
	}
	dg[1]=SZ(v[1])+1;
	while(SZ(que)){
		ll i=que.front();que.pop();
		dp[i]=Q(i,i);
		for(auto j:q[i]){
			dp[i]=max(dp[i],j.X+Q(i,j.Y.X)+Q(i,j.Y.Y)-Q(i,i));
		}
		ins(1,0,n,to[i],-dp[i]);
		ins(1,0,n,to[fa[i]],dp[i]);
		for(auto j:v[i]){
			--dg[j];
			if(dg[j]==1)que.push(j);
		}
	} 
	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