Submission #754991

#	Time	Username	Problem	Language	Result	Execution time	Memory
754991		jmyszka2007	Election Campaign (JOI15_election_campaign)	C++17	10 / 100	137 ms	29980 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pi pair<int, int>
#define pb push_back
constexpr int LIM = 1e5;
vector<int>g[LIM + 10];
int pre[LIM + 10];
int post[LIM + 10];
int nxt[LIM + 10][18];
int dp[LIM + 10][2];
vector<pair<pi, pi> >zap[LIM + 10];
bool czy(int a, int b) {
	return pre[a] <= pre[b] && post[a] >= post[b];
}
pi lca(int a, int b) {
	if(pre[a] <= pre[b]) {
		swap(a, b);
	}
	for(int i = 17; i >= 0; i--) {
		if(!czy(nxt[a][i], b)) {
			a = nxt[a][i];
		}
	}
	return {a, nxt[a][0]};
}
int aktpre = 1, aktpost = 1;
void dfs(int v, int o) {
	pre[v] = aktpre++;
	nxt[v][0] = o;
	for(int i = 1; i <= 17; i++) {
		nxt[v][i] = nxt[nxt[v][i - 1]][i - 1];
	}
	for(auto x : g[v]) {
		if(x != o) {
			dfs(x, v);
		}
	}
	post[v] = aktpost++;
}
void cntdp(int v, int o) {
	int sum = 0;
	for(auto x : g[v]) {
		if(x != o) {
			cntdp(x, v);
			sum += max(dp[x][0], dp[x][1]);
		}
	}
	dp[v][0] = sum;
	for(auto x : zap[v]) {
		if(x.nd.st == v) {
			dp[v][1] = max(dp[v][1], sum - max(dp[x.st.nd][0], dp[x.st.nd][1]) + dp[x.nd.nd][0] + x.st.st);
		}
		else if(x.nd.nd == v) {
			dp[v][1] = max(dp[v][1], sum - max(dp[x.st.nd][0], dp[x.st.nd][1]) + dp[x.nd.st][0] + x.st.st);
		}
		else {
			dp[v][1] = max(dp[v][1], sum - max(dp[x.st.nd][0], dp[x.st.nd][1]) + dp[x.nd.nd][0] + dp[x.nd.st][0] + x.st.st);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for(int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(1, 1);
	int t;
	cin >> t;
	for(int i = 1; i <= t; i++) {
		int a, b, x;
		cin >> a >> b >> x;
		pi tmp = lca(a, b);
		zap[tmp.nd].pb({{x, tmp.st}, {a, b}});
	}
	cntdp(1, 1);
	cout << max(dp[1][0], dp[1][1]);
}

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