Submission #366545

#	Time	Username	Problem	Language	Result	Execution time	Memory
366545		Rainbowbunny	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	531 ms	36736 KiB

election_campaign

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <chrono>
#include <random>
#include <bitset>
#include <utility>

int n, timer;
int tin[100005], tout[100005], up[20][100005];
std::vector <int> Adj[100005];

int m;
int A[100005], B[100005], C[100005];
int dp[100005];
std::vector <int> Query[100005];

int BIT[100005];

void Add(int id, int value)
{
	for(id; id <= n; id += id & -id)
	{
		BIT[id] += value; 
	}
}

int Get(int id)
{
	int ans = 0;
	for(id; id > 0; id -= id & -id)
	{
		ans += BIT[id];
	}
	return ans;
}

void DFS(int node, int p)
{
	timer++;
	tin[node] = timer;
	up[0][node] = p;
	for(int i = 1; i <= 19; i++)
	{
		up[i][node] = up[i - 1][up[i - 1][node]];
	}
	for(auto x : Adj[node])
	{
		if(x == p)
		{
			continue;
		}
		DFS(x, node);
	}
	tout[node] = timer;
}

int Isparent(int u, int v)
{
	return tin[u] <= tin[v] and tout[u] >= tout[v];
}

int LCA(int u, int v)
{
	if(Isparent(u, v))
	{
		return u;
	}
	for(int i = 19; i >= 0; i--)
	{
		if(!Isparent(up[i][u], v))
		{
			u = up[i][u];
		}
	}
	return up[0][u];
}

int Subtree(int u, int v)
{
	assert(Isparent(u, v));
	for(int i = 19; i >= 0; i--)
	{
		if(!Isparent(up[i][v], u))
		{
			v = up[i][v];
		}
	}
	return v;
}

void Caldp(int node, int p)
{
	int sumdp = 0;
	for(auto x : Adj[node])
	{
		if(x == p)
		{
			continue;
		}
		Caldp(x, node);
		sumdp += dp[x];
		dp[node] = std::max(dp[node], dp[x]);
	}
	dp[node] = std::max(dp[node], sumdp);
	for(auto x : Query[node])
	{
		if(A[x] == B[x])
		{
			dp[node] = std::max(dp[node], sumdp + C[x]);
		}
		else if(A[x] == node)
		{
			dp[node] = std::max(dp[node], sumdp - dp[Subtree(A[x], B[x])] + Get(tin[B[x]]) + C[x]);	
		}
		else if(B[x] == node)
		{
			dp[node] = std::max(dp[node], sumdp - dp[Subtree(B[x], A[x])] + Get(tin[A[x]]) + C[x]);
		}
		else
		{
			dp[node] = std::max(dp[node], sumdp - dp[Subtree(node, A[x])] - dp[Subtree(node, B[x])] + Get(tin[A[x]]) + Get(tin[B[x]]) + C[x]);
		}
	}
	for(auto x : Adj[node])
	{
		if(x == p)
		{
			continue;
		}
		Add(tin[x], sumdp - dp[x]);
		Add(tout[x] + 1, dp[x] - sumdp);
	}
	Add(tin[node], sumdp);
	Add(tin[node] + 1, -sumdp);
}

int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin >> n;
	for(int i = 1; i < n; i++)
	{
		int u, v;
		std::cin >> u >> v;
		Adj[u].push_back(v);
		Adj[v].push_back(u);
	}
	DFS(1, 1);
	std::cin >> m;
	for(int i = 1; i <= m; i++)
	{
		std::cin >> A[i] >> B[i] >> C[i];
		Query[LCA(A[i], B[i])].push_back(i);
	}
	Caldp(1, 1);
	std::cout << *std::max_element(dp + 1, dp + n + 1);
}

Compilation message (stderr)

election_campaign.cpp: In function 'void Add(int, int)':
election_campaign.cpp:29:6: warning: statement has no effect [-Wunused-value]
   29 |  for(id; id <= n; id += id & -id)
      |      ^~
election_campaign.cpp: In function 'int Get(int)':
election_campaign.cpp:38:6: warning: statement has no effect [-Wunused-value]
   38 |  for(id; id > 0; id -= id & -id)
      |      ^~

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 30 / 30
• Subtask 5: 10 / 10
• Subtask 6: 40 / 40