Submission #906268

#	Time	Username	Problem	Language	Result	Execution time	Memory
906268		OAleksa	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	297 ms	44540 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
const int N = 1e5 + 69;
const int K = 17;
int up[N][K];
int n, m, st[4 * N], id[N], sz[N], dep[N], top[N];
int dp[N];
vector<int> g[N];
vector<tuple<int, int, int>> q[N];
int tin[N], tout[N], timer;
int anc(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int Lca(int a, int b) {
	if (anc(a, b))
		return a;
	else if (anc(b, a))
		return b;
	for (int i = K - 1;i >= 0;i--) {
		if (!anc(up[a][i], b) && up[a][i] > 0)
			a = up[a][i];
	}
	return up[a][0];
}
void dfs(int v, int p) {
	up[v][0] = p;
	tin[v] = ++timer;
	dep[v] = dep[p] + 1;
	sz[v] = 1;
	for (int i = 1;i < K;i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
	for (auto u : g[v]) {
		if (u == p)
			continue;
		dfs(u, v);
		sz[v] += sz[u];
	}
	tout[v] = timer;
}
int x;
void hld(int v, int p, int c) {
	top[v] = c;
	id[v] = ++x;
	int mx = 0, s = -1;
	for (auto u : g[v]) {
		if (u == p)
			continue;
		if (sz[u] > mx) {
			mx = sz[u];
			s = u;
		}
	}
	if (s == -1)
		return;
	hld(s, v, c);
	for (auto u : g[v]) {
		if (u == p || u == s)
			continue;
		hld(u, v, u);
	}
}
void modify(int v, int tl, int tr, int p, int x) {
	if (tl == tr)
		st[v] = x;
	else {
		int mid = (tl + tr) / 2;
		if (p <= mid)
			modify(v * 2, tl, mid, p, x);
		else
			modify(v * 2 + 1, mid + 1, tr, p, x);
		st[v] = st[v * 2] + st[v * 2 + 1];
	}
}
int Get(int v, int tl, int tr, int l, int r) {
	if (tl > r || tr < l)
		return 0;
	else if (tl >= l && tr <= r)
		return st[v];
	else {
		int mid = (tl + tr) / 2;
		return Get(v * 2, tl, mid, l, r) + Get(v * 2 + 1, mid + 1, tr, l, r);
	}
}
int Get(int x, int y) {
	int res = 0;
	while (top[x] != top[y]) {
		res += Get(1, 1, n, id[top[x]], id[x]);
		x = up[top[x]][0];
	}
	res += Get(1, 1, n, id[y], id[x]);
	return res;
}
void solve(int v, int p) {
	int s = 0;
	for (auto u : g[v]) {
		if (u == p)
			continue;
		solve(u, v);
		s += dp[u];
	}
	dp[v] = s;
	for (auto u : q[v]) {
		int a, b, c;
		tie(a, b, c) = u;
		dp[v] = max(dp[v], s + Get(a, v) + Get(b, v) + c);
	}
	modify(1, 1, n, id[v], s - dp[v]);
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n;
		for (int i = 1;i <= n - 1;i++) {
		 	int a, b;
		 	cin >> a >> b;
		 	g[a].push_back(b);
		 	g[b].push_back(a);
		}
		dfs(1, 0);
		hld(1, 0, 1);
		cin >> m;
		for (int i = 1;i <= m;i++) {
			int a, b, c;
			cin >> a >> b >> c;
			int lca = Lca(a, b);
			q[lca].push_back({a, b, c});
		}
		solve(1, 0);
		cout << dp[1] << '\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