Submission #156562

#TimeUsernameProblemLanguageResultExecution timeMemory
156562SaboonElection Campaign (JOI15_election_campaign)C++14
100 / 100
458 ms38020 KiB
#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]);
					s[c[v]].erase(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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...