Submission #156560

#	Time	Username	Problem	Language	Result	Execution time	Memory
156560		Saboon	Election Campaign (JOI15_election_campaign)	C++14	10 / 100	459 ms	35064 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;

vector<int> t[maxn], vec[maxn];
int dp[maxn], mx[maxn], c[maxn], lazy[maxn], cost[maxn], w[maxn];
set<int> s[maxn];

void dfs(int v, int p = -1){
	int sum = 0;
	for (auto u : t[v])
		if (u != p)
			dfs(u, v), sum += dp[u];
	dp[v] = sum + mx[v];
	for (auto u : t[v])
		if (u != p)
			lazy[c[u]] += sum - dp[u];
	for (auto u : t[v]){
		if (u != p){
			if (s[c[u]].size() > s[c[v]].size())
				swap(c[v], c[u]);
			for (auto idx : s[c[u]]){
				if (s[c[v]].find(idx) != s[c[v]].end())
					dp[v] = max(dp[v], cost[idx] + lazy[c[v]] + lazy[c[u]] - sum + w[idx]);
				else
					s[c[v]].insert(idx), cost[idx] += lazy[c[u]] - lazy[c[v]];
			}
			s[c[u]].clear();
		}
	}
	for (auto idx : vec[v]){
		if (s[c[v]].find(idx) == s[c[v]].end())
			s[c[v]].insert(idx), cost[idx] = sum - lazy[c[v]];
		else
			dp[v] = max(dp[v], cost[idx] + lazy[c[v]] + w[idx]);
	}
}

int main(){
	ios_base::sync_with_stdio (false);
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++){
		int v, u;
		cin >> v >> u;
//		v --, u --;
		t[v].push_back(u);
		t[u].push_back(v);
	}
	int m;
	cin >> m;
	for (int i = 1; i <= n; i++)
		c[i] = i;
	for (int i = 1; i <= m; i++){
		int v, u;
		cin >> v >> u >> w[i];
		if (v == u){
			mx[v] = max(mx[v], w[i]);
			continue;
		}
		vec[v].push_back(i);
		vec[u].push_back(i);
	}
	dfs(1);
	cout << dp[1] << endl;
}

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