Submission #417557

#	Time	Username	Problem	Language	Result	Execution time	Memory
417557		MohamedAhmed04	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	240 ms	34048 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e5 + 10 ;

int n , m ;

int P[MAX][17] , dep[MAX] ;
int in[MAX] , out[MAX] ;

vector< vector<int> >adj(MAX) ;

int tim = 0 ;

void dfs(int node , int par)
{
	in[node] = ++tim ;
	P[node][0] = par ;
	for(int j = 1 ; j < 17 ; ++j)
		P[node][j] = P[P[node][j-1]][j-1] ;
	for(auto &child : adj[node])
	{
		if(child == par)
			continue ;
		dep[child] = dep[node] + 1 ;
		dfs(child , node) ;
	}
	out[node] = tim ;
}

int kth_ancestor(int node , int k)
{
	for(int j = 16 ; j >= 0 ; --j)
	{
		if((1 << j) <= k)
			node = P[node][j] , k -= (1 << j) ;
	}
	return node ;
}

int LCA(int x , int y)
{
	if(dep[x] < dep[y])
		swap(x , y) ;
	for(int j = 16 ; j >= 0 ; --j)
	{
		if(dep[x] - (1 << j) >= dep[y])
			x = P[x][j] ;
	}
	if(x == y)
		return x ;
	for(int j = 16 ; j >= 0 ; --j)
	{
		if(P[x][j] != P[y][j])
			x = P[x][j] , y = P[y][j] ;
	}
	return P[x][0] ;
}

int bit[MAX] ;

void add(int i , int x)
{
	for(; i <= n ; i += (i & (-i)))
		bit[i] += x ;
}

int get(int i)
{
	int sum = 0 ;
	for(; i > 0 ; i -= (i & (-i)))
		sum += bit[i] ;
	return sum ;
}

vector< array<int , 3> >v[MAX] ;

int dp[MAX] ;

void dfs2(int node , int par)
{
	int sum = 0 ;
	for(auto &child : adj[node])
	{
		if(child == par)
			continue ;
		dfs2(child , node) ;
		sum += dp[child] ;
	}
	add(in[node] , sum) ;
	add(in[node]+1 , -sum) ;
	dp[node] = sum ;
	for(auto &a : v[node])
	{
		int x = a[0] , y = a[1] , z = a[2] ;
		int now = sum + z ;
		if(x != node)
			now += get(in[x]) , now -= dp[kth_ancestor(x , dep[x] - dep[node] - 1)] ;
		if(y != node)
			now += get(in[y]) , now -= dp[kth_ancestor(y , dep[y] - dep[node] - 1)] ;
		dp[node] = max(dp[node] , now) ;
	}
	for(auto &child : adj[node])
	{
		if(child == par)
			continue ;
		sum -= dp[child] ;
		add(in[child] , sum) ;
		add(out[child]+1 , -sum) ;
		sum += dp[child] ;
	}
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 0 ; i < n-1 ; ++i)
	{
		int x , y ;
		cin>>x>>y ;
		adj[x].push_back(y) ;
		adj[y].push_back(x) ;
	}
	dfs(1 , 0) ;
	int m ;
	cin>>m ;
	while(m--)
	{
		int x , y , z ;
		cin>>x>>y>>z ;
		v[LCA(x , y)].push_back({x , y , z}) ;
	}
	dfs2(1 , 0) ;
	return cout<<dp[1]<<"\n" , 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