Submission #87781

#	Time	Username	Problem	Language	Result	Execution time	Memory
87781		MB81	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	955 ms	161648 KiB

election_campaign

// Ala be zekrellah tatmaenolgholoob ...
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define F first
#define S second
#define MP make_pair
const int maxn = 2e5+9;
const int lg = 19;
const ll mod = 1e9+7;

vector <int> g[maxn];
vector <pair<pii,int>> vec[maxn], edge[maxn];
int n, m;
int par[maxn][lg], sum[maxn][lg], sub[maxn], h[maxn], curchild[maxn], dp[maxn];

int lca (int v, int u) {
	if (h[v] < h[u]) swap(v, u);
	for (int i = lg - 1; i >= 0; i--)
		if (par[v][i] + 1 && h[par[v][i]] >= h[u])
			v = par[v][i];
	if (v == u)
		return v;
	for (int i = lg - 1; i >= 0; i--)
		if (par[v][i] != par[u][i]) {
			v = par[v][i];
			u = par[u][i];
		}
	return par[v][0];
}

int get (int v, int u) {
	int res = 0;
	for (int i = lg - 1; i >= 0; i--)
		if (par[v][i] + 1 && h[par[v][i]] >= h[u]) {
			res += sum[v][i];
			v = par[v][i];
		}
	return res;
}

void dfs0 (int v, int parent = -1) {
	par[v][0] = parent;
	if (parent + 1) {
		h[v] = h[parent] + 1;
		vec[parent].push_back( MP( MP( v, 0 ), v ) );
	}
	for (int i = 1; i < lg; i++)
		if (par[v][i - 1] + 1) {
			par[v][i] = par[par[v][i - 1]][i - 1];
			if (par[v][i] + 1)
			vec[par[v][i]].push_back( MP( MP( v, i ), curchild[par[v][i]]) );
		}
	for (auto u : g[v]) {
		if (u == parent) continue;
		curchild[v] = u;
		dfs0(u, v);
	}
	return;
}

void dfs (int v, int parent = -1) {
	for (auto u : g[v]) {
	    if (u == parent) continue;
		dfs(u, v);
		sub[v] += dp[u];
	}
	for (auto x : vec[v]) {
		int u = x.F.F, depth = x.F.S, firstchild = x.S;
		sum[u][depth] = 1LL * get(u, firstchild) + sub[v] - dp[firstchild];
	}
	dp[v] = sub[v];
	for (auto e : edge[v]) {
		int x = e.F.F, y = e.F.S, c = e.S;
		if (x == v || y == v) {
			if (y == v) swap(x, y);
			dp[v] = max(1LL * dp[v], 1LL * get(y, v) + sub[y] + c);
		}
		else
			dp[v] = max(1LL * dp[v], 1LL * get(x, v) + get(y, v) - sub[v] + sub[x] + sub[y] + c);
	}
	return;
}

int main () {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i < n; i++) {
	    int v, u;
	    cin >> v >> u;
		--v; --u;
		g[v].push_back( u );
		g[u].push_back( v );
	}
	memset(par, -1, sizeof par);
	dfs0(0);
	cin >> m;
	for (int i = 0; i < m; i++) {
		int v, u, c;
		cin >> v >> u >> c;
		--v, --u;
		edge[lca(v, u)].push_back( MP( MP( v, u ), c ) );
	}
	dfs(0);
	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