Submission #296055

#	Time	Username	Problem	Language	Result	Execution time	Memory
296055		Berted	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	259 ms	28536 KiB

election_campaign

#include <iostream>
#include <vector>
#define ll long long
#define pii pair<int, int>
#define ppi pair<pii, int>
#define fst first
#define snd second
using namespace std;

const int LG = 17;

struct BIT
{
	int N; ll A[100001];
	BIT() {}
	BIT(int size) {N = size;}
	void init(int size) {N = size;}
	void update(int x, ll val)
	{
		for (; x <= N; x += x & (-x)) {A[x] += val;}
	}
	ll query(int x)
	{
		ll ret = 0;
		for (; x; x -= x & (-x)) {ret += A[x];}
		return ret;
	}
};

int N, Q, h[100001], L[100001], R[100001], sps[100001][LG], idx = 1;
BIT D1, D2;
ll DP[100001];
vector<int> adj[100001];
vector<ppi> solve[100001];

void prep(int u, int p)
{
	h[u] = (p == -1) ? 0 : (h[p] + 1); L[u] = R[u] = idx++;
	sps[u][0] = p;
	for (int i = 1; i < LG; i++)
	{
		if (sps[u][i - 1] != -1) sps[u][i] = sps[sps[u][i - 1]][i - 1];
		else sps[u][i] = -1;
	}
	for (auto v : adj[u])
	{
		if (v != p)
		{
			prep(v, u);
			R[u] = max(R[u], R[v]);
		}
	}
}

inline int getLCA(int u, int v)
{
	if (h[u] > h[v]) {swap(u, v);}
	for (int i = 0; h[v] - h[u]; i++)
	{
		if ((h[v] - h[u]) & (1 << i)) {v = sps[v][i];}
	}
	if (u == v) {return u;}
	for (int i = LG - 1; i >= 0; i--)
	{
		if (sps[u][i] != sps[v][i]) {u = sps[u][i]; v = sps[v][i];}
	}
	return sps[u][0];
}

void DFS(int u, int p)
{
	ll childSum = 0;
	for (auto v : adj[u])
	{
		if (v != p) {DFS(v, u); childSum += DP[v];}
	}

	DP[u] = childSum;
	for (auto v : solve[u])
	{
		ll v1 = D1.query(L[v.fst.fst]) + D1.query(L[v.fst.snd]);
		ll v2 = D2.query(L[v.fst.fst]) + D2.query(L[v.fst.snd]);
		DP[u] = max(DP[u], v1 - v2 + childSum + v.snd);
	}

	D1.update(L[u], childSum);
	D1.update(R[u] + 1, -childSum);
	D2.update(L[u], DP[u]);
	D2.update(R[u] + 1, -DP[u]);
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N; D1.init(N); D2.init(N);
	for (int i = 1; i < N; i++)
	{
		int u, v; cin >> u >> v;
		adj[u - 1].push_back(v - 1);
		adj[v - 1].push_back(u - 1);
	}
	prep(0, -1);
	cin >> Q;
	for (int i = 0; i < Q; i++)
	{
		int u, v, w; cin >> u >> v >> w; u--; v--;
		solve[getLCA(u, v)].push_back({{u, v}, w});
	}
	DFS(0, -1);
	cout << DP[0] << "\n";
	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