Submission #1177932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177932		altern23	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	134 ms	40776 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 1e5;
const ll INF = 4e18;
const int MOD = 1e9 + 7;

vector<ll> adj[MAXN + 5];
vector<pair<pii, ll>> isi[MAXN + 5];
ll up[MAXN + 5][20], dist[MAXN + 5], dp[MAXN + 5][2];
ll tin[MAXN + 5], tout[MAXN + 5];

struct fenwick{
	ll n;
	vector<ll> bit;
	fenwick(ll _n){
		n = _n;
		bit.resize(n + 5);
	}
	void upd(ll idx, ll val) { for(int i = idx; i <= n; i += i & -i) bit[i] += val; }
	ll get(ll idx) { ll ans = 0; for(int i = idx; i >= 1; i -= i & -i) ans += bit[i]; return ans; }
};

fenwick bit1(MAXN), bit2(MAXN);

ll cur = 0;

void dfs1(ll idx, ll par){
	tin[idx] = ++cur;
	for(auto i : adj[idx]){
		if(i != par){
			up[i][0] = idx;
			dist[i] = dist[idx] + 1;
			dfs1(i, idx);
		}
	}
	tout[idx] = cur;
}

void dfs2(ll idx, ll par){
	ll sum = 0;
	for(auto i : adj[idx]){
		if(i != par){
			dfs2(i, idx);
			sum += max(dp[i][0], dp[i][1]);
		}
	}
	dp[idx][0] = sum;
	for(auto [path, c] : isi[idx]){
		ll a = bit1.get(tin[path.fi]) - bit2.get(tin[path.fi]);
		ll b = bit1.get(tin[path.sec]) - bit2.get(tin[path.sec]);
		dp[idx][1] = max(dp[idx][1], sum + a + b + c);
	}
	bit1.upd(tin[idx], sum);
	bit1.upd(tout[idx] + 1, -sum);
	bit2.upd(tin[idx], max(dp[idx][0], dp[idx][1]));
	bit2.upd(tout[idx] + 1, -max(dp[idx][0], dp[idx][1]));
}
	
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;	
	// cin >> tc;	
	for(;tc--;){
		ll N; cin >> N;
		for(int i = 2; i <= N; i++){
			ll u, v; cin >> u >> v;
			adj[u].push_back(v), adj[v].push_back(u);
		}
		
		dfs1(1, -1);
		
		for(int LOG = 1; LOG < 20; LOG++){
			for(int i = 1; i <= N; i++) up[i][LOG] = up[up[i][LOG - 1]][LOG - 1];
		}
		
		auto get_lca = [&](ll a, ll b){
			if(dist[a] < dist[b]) swap(a, b);
			ll res = dist[a] - dist[b];
			for(int LOG = 0; LOG < 20; LOG++){
				if(res & (1LL << LOG)) a = up[a][LOG];
			}
			if(a == b) return a;
			for(int LOG = 19; LOG >= 0; --LOG){
				if(up[a][LOG] != up[b][LOG]) a = up[a][LOG], b = up[b][LOG];
			}
			return up[a][0];
		};
		
		ll M; cin >> M;
		for(int i = 1; i <= M; i++){
			ll a, b, c; cin >> a >> b >> c;
			isi[get_lca(a, b)].push_back({{a, b}, c});
		}
		
		dfs2(1, -1);
		cout << max(dp[1][0], dp[1][1]) << "\n";
	}   
	
}

/*


*/

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