제출 #1331574

#제출 시각아이디문제언어결과실행 시간메모리
1331574boclobanchatElection Campaign (JOI15_election_campaign)C++20
0 / 100
104 ms17252 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],dis[MAXN],sp[MAXN][20];
void dfs(int i,int pre)
{
	sp[i][0]=pre;
	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);
	}
}
int shift(int i,int k)
{
	if(k<0) return i;
	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 sum=0;
	for(auto v:ds[i]) if(v!=pre)
	{
		dfs2(v,i);
		sum+=dp[v];
	}
	dp[i]=sum;
	for(auto v:vi[i]) dp[i]=max(dp[i],sum-dp[v.x]*(v.x!=i)-dp[v.y]*(v.y!=i)+v.val);
}
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({shift(l,dis[l]-dis[lc]-1),shift(r,dis[r]-dis[lc]-1),v});
	}
	dfs2(1,1);
	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...