제출 #1296450

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1296450		Jawad_Akbar_JJ	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	189 ms	31484 KiB

election_campaign

#include <iostream>
#include <vector>

using namespace std;
const int N = 1<<17;
int dp[N], ft[N], ch[N], chSum[N], Par[N][20], hei[N], st[N], cur;
vector<int> nei[N];
vector<pair<int, pair<int, int>>> Vec[N];

void Add(int i, int v){
	for (; i < N; i += i & -i)
		ft[i] += v;
}
int get(int i, int ans = 0){
	for (; i; i -= i & -i)
		ans += ft[i];
	return ans;
}

void dfs(int u, int p){
	Par[u][0] = p, hei[u] = hei[p] + 1, st[u] = ++cur, ch[u] = 1;
	for (int i=0;i<17;i++)
		Par[u][i+1] = Par[Par[u][i]][i];

	for (int i : nei[u]){
		if (i == p)
			continue;
		dfs(i, u);
		ch[u] += ch[i];
	}
}

void dfs2(int u, int p){
	for (int i : nei[u]){
		if (i == p)
			continue;
		dfs2(i, u);
		chSum[u] += dp[i];
	}

	dp[u] = chSum[u];
	for (auto [c, lr] : Vec[u]){
		auto [l, r] = lr;
		auto [l1, r1] = lr;

		for (int i=17;i>=0;i--){
			if (hei[u] + (1<<i) < hei[l1])
				l1 = Par[l1][i];
			if (hei[u] + (1<<i) < hei[r1])
				r1 = Par[r1][i];
		}

		if (l == r)
			dp[u] = max(dp[u], chSum[u] + c);
		else if (l == u)
			dp[u] = max(dp[u], chSum[u] - dp[r1] + chSum[r] + get(st[r]) + c);
		else
			dp[u] = max(dp[u], chSum[u] - dp[r1] - dp[l1] + chSum[l] + chSum[r] + get(st[r]) + get(st[l]) + c);
	}

	for (int i : nei[u]){
		if (i == p)
			continue;
		Add(st[i], chSum[u] - dp[i]);
		Add(st[i] + ch[i], dp[i] - chSum[u]);
	}
}

int LCA(int u, int v){
	if (hei[u] > hei[v])
		swap(u, v);

	for (int i=17;i>=0;i--){
		if (hei[u] + (1<<i) <= hei[v])
			v = Par[v][i];
	}

	for (int i=17;i>=0;i--){
		if (Par[u][i] != Par[v][i])
			u = Par[u][i], v = Par[v][i];
	}
	return (u == v ? u : Par[u][0]);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, q;
	cin>>n;

	for (int i=1;i<n;i++){
		int a, b;
		cin>>a>>b;

		nei[a].push_back(b);
		nei[b].push_back(a);
	}

	dfs(1, 0);


	cin>>q;
	for (int i=1;i<=q;i++){
		int l, r, c;
		cin>>l>>r>>c;

		if (hei[l] > hei[r])
			swap(l, r);
		Vec[LCA(l, r)].push_back({c, {l, r}});
	}
	dfs2(1, 0);

	cout<<dp[1]<<endl;
}

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