Submission #1303811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303811		jungle15	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	110 ms	27840 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;

#define _(x) ((x) & -(x))
#define getbit(x, i) (((x) >> (i)) & 1)

template <typename t>
void maxi(t &a, t b)
{
	if(a < b)
		a = b;
}

const int maxn = 1e5;

int n, nq;
vector<int> adj[maxn + 2];
vector<tuple<int, int, int>> cands[maxn + 2];

void init(void)
{
	cin >> n;
	for(int i = 1; i < n; ++i)
	{
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	cin >> nq;
}

const int maxlog = 20;

struct Fenwick
{
	int bit[maxn + 2];

	Fenwick(void)
	{
		memset(bit, 0, sizeof(bit));
	}

	void update(int x, const int val)
	{
		for(; x <= n; x += _(x))
			bit[x] += val;
	}

	void update(const int l, const int r, const int val)
	{
		update(l, val);
		update(r + 1, -val);
	}

	int get(int x)
	{
		int ans = 0;
		for(; x; x -= _(x))
			ans += bit[x];
		return ans;
	}
} bit;

int timer, tin[maxn + 2], par[maxn + 2][maxlog], tout[maxn + 2], depth[maxn + 2];

void pre_DFS(const int u = 1)
{
	tin[u] = ++timer;
	for(const int &v : adj[u])
	{
		if(v == par[u][0])
			continue;
		depth[v] = depth[u] + 1;
		par[v][0] = u;
		for(int i = 1; i < maxlog; ++i)
			par[v][i] = par[par[v][i - 1]][i - 1];
		pre_DFS(v);
	}
	tout[u] = timer;
}

int lca(int u, int v)
{
	if(depth[u] > depth[v])
		swap(u, v);
	int diff = depth[v] - depth[u];
	for(int i = 0; i < maxlog; ++i)
		if(getbit(diff, i))
			v = par[v][i];
	if(u == v)
		return u;
	for(int i = maxlog - 1; i > -1; --i)
		if(par[u][i] != par[v][i])
		{
			u = par[u][i];
			v = par[v][i];
		}
	return par[u][0];
}

int dp[maxn + 2];

void DFS(const int u = 1)
{
	int sum = 0;
	for(const int &v : adj[u])
	{
		if(v == par[u][0])
			continue;
		DFS(v);
		sum += dp[v];
	}
	dp[u] = sum;
	for(const auto &[x, y, w] : cands[u])
		maxi(dp[u], bit.get(tin[x]) + bit.get(tin[y]) + w + sum);
	bit.update(tin[u], tout[u], sum - dp[u]);
}

void solve(void)
{
	init();
	pre_DFS();
	for(; nq; --nq)
	{
		int u, v, w;
		cin >> u >> v >> w;
		cands[lca(u, v)].push_back({u, v, w});
	}
	DFS();
	cout << dp[1];
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);

	solve();

	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