Submission #239989

#	Time	Username	Problem	Language	Result	Execution time	Memory
239989		MvC	Election Campaign (JOI15_election_campaign)	C++11	100 / 100	214 ms	30968 KiB

election_campaign

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define lun(x) (int)x.size()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<60);
const int inf=(1<<30);
const int nmax=1e5+50;
const ll mod=1e9+7;
using namespace std;
int x,y,z,c[nmax],ex[nmax],ey[nmax],i,n,up[nmax][20],tin[nmax],tout[nmax],t,f[nmax],dp[nmax],fw[nmax],m;
vector<int>a[nmax],vc[nmax];
void dfs(int x,int p)
{
    tin[x]=++t;
    up[x][0]=p;
    for(int i=1;i<17;i++)up[x][i]=up[up[x][i-1]][i-1];
    for(int i=0;i<lun(a[x]);i++)if(a[x][i]!=p)dfs(a[x][i],x);
    tout[x]=t;
}
int anc(int x,int y)
{
    return tin[x]<=tin[y] && tout[x]>=tout[y];
}
int lca(int x,int y)
{
    if(anc(x,y))return x;
    if(anc(y,x))return y;
    for(int i=16;i>=0;i--)if(!anc(up[x][i],y))x=up[x][i];
    return up[x][0];
}
void ufw(int i,int v)
{
	for(;i<=n;i+=i&(-i))fw[i]+=v;
}
int qfw(int i)
{
	ll ans=0;
	for(;i>=1;i-=i&(-i))ans+=fw[i];
	return ans;
}
void asd(int x,int p)
{
	for(int i=0;i<lun(a[x]);i++)
	{
		int y=a[x][i];
		if(y==p)continue;
		asd(y,x);
		dp[x]+=f[y];
	}
	f[x]=dp[x];
	ufw(tin[x],dp[x]);
	ufw(tout[x]+1,-dp[x]);
	for(int i=0;i<lun(vc[x]);i++)
	{
		int u=ex[vc[x][i]],v=ey[vc[x][i]],z=c[vc[x][i]];
		f[x]=max(f[x],qfw(tin[u])+qfw(tin[v])-dp[x]+z);
	}
	ufw(tin[x],-f[x]);
	ufw(tout[x]+1,f[x]);
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n;
	for(i=1;i<n;i++)
	{
		cin>>x>>y;
		a[x].pb(y);
		a[y].pb(x);
	}
	dfs(1,1);
	cin>>m;
	for(i=1;i<=m;i++)
	{
		cin>>x>>y>>z;
		vc[lca(x,y)].pb(i);
		ex[i]=x,ey[i]=y,c[i]=z;
	}
	asd(1,1);
	cout<<f[1]<<endl;
	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