Submission #1331670

#TimeUsernameProblemLanguageResultExecution timeMemory
1331670boclobanchatElection Campaign (JOI15_election_campaign)C++20
100 / 100
137 ms29784 KiB
#include<bits/stdc++.h>
using namespace std;
struct vote
{
	int x,y,val;
};
const int MAXN=1e5+5;
vector<int> ds[MAXN];
vector<vote> vi[MAXN];
int dp[MAXN],sa[MAXN],dis[MAXN],sp[MAXN][20],fen[MAXN],L[MAXN],R[MAXN],tdfs=0;
void update(int i,int n,int val) { for(;i<=n;i+=i&-i) fen[i]+=val; }
int get(int i) { int ans=0;for(;i;i-=i&-i) ans+=fen[i];return ans; }
void dfs(int i,int pre)
{
	sp[i][0]=pre,L[i]=++tdfs;
	for(int j=1;j<=17;j++) sp[i][j]=sp[sp[i][j-1]][j-1];
	for(auto v:ds[i]) if(v!=pre)
	{
		dis[v]=dis[i]+1;
		dfs(v,i);
	}
	R[i]=tdfs;
}
int shift(int i,int k)
{
	for(int j=17;j+1;j--) if(k&(1<<j)) i=sp[i][j];
	return i;
}
int lca(int a,int b)
{
	int x=dis[a],y=dis[b],m=min(x,y);
	for(int i=17;i+1;i--)
	{
		if((x-m)&(1<<i)) a=sp[a][i];
		if((y-m)&(1<<i)) b=sp[b][i];
	}
	if(a==b) return a;
	for(int i=17;i+1;i--) if(sp[a][i]!=sp[b][i]) a=sp[a][i],b=sp[b][i];
	return sp[a][0];
}
void dfs2(int i,int pre,int n)
{
	int sum=0;
	for(auto v:ds[i]) if(v!=pre)
	{
		dfs2(v,i,n);
		sum+=dp[v];
	}
	dp[i]=sa[i]=sum;
	for(auto v:vi[i])
	{
		int res=sum+v.val;
		if(v.x!=i) res=res-dp[shift(v.x,dis[v.x]-dis[i]-1)]+get(L[v.x])+sa[v.x];
		if(v.y!=i) res=res-dp[shift(v.y,dis[v.y]-dis[i]-1)]+get(L[v.y])+sa[v.y];
		dp[i]=max(dp[i],res);
	}
	for(auto v:ds[i]) if(v!=pre)
	{
		update(L[v],n,sum-dp[v]);
		update(R[v]+1,n,dp[v]-sum);
	}
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n;
    for(int i=1;i<n;i++)
    {
    	int l,r;
    	cin>>l>>r;
    	ds[l].push_back(r),ds[r].push_back(l);
	}
	dfs(1,1);
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		int l,r,v;
		cin>>l>>r>>v;
		int lc=lca(l,r);
		vi[lc].push_back({l,r,v});
	}
	dfs2(1,1,n);
	cout<<dp[1];
}
#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...