Submission #890614

#	Time	Username	Problem	Language	Result	Execution time	Memory
890614		iskhakkutbilim	Election Campaign (JOI15_election_campaign)	C++17	30 / 100	1055 ms	34384 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 100000;

int n;
vector<int> g[N+5];
int timer, depth[N+10], sub[N+10];
int up[N + 10][18], bigchild[N+10], chain[N+10];
int pos[N+10];
void dfs(int v, int par){
	up[v][0] = par;
	sub[v] = 1;
	for(int j = 1; j < 18; j++){
		up[v][j] = up[up[v][j-1]][j-1];
	}
	for(int to : g[v]){
		if(to == par) continue;
		depth[to] = depth[v] + 1;
		dfs(to, v);
		sub[v]+= sub[to];
		if(!bigchild[to] || sub[bigchild[v]] < sub[to]){
			bigchild[v] = to;
		}
	}
}


void decompose(int v, int par, int head){
	chain[v] = head;
	pos[v] = timer++;
	if(bigchild[v]){
		decompose(bigchild[v], v, head);
	}
	for(int to : g[v]){
		if(to == par || to == bigchild[v]) continue;
		decompose(to, v, to);
	}
}

int lca(int a, int b){
	if(depth[a] > depth[b]) swap(a, b);
	int k = depth[b] - depth[a];
	for(int i = 0;i < 18; i++){
		if(k & (1<<i)){
			b = up[b][i];
		}
	}
	if(a == b) return a;
	for(int i = 17; i >= 0; i--){
		if(up[a][i] != up[b][i]){
			a = up[a][i];
			b = up[b][i];
		}
	}
	return up[a][0];
}
long long t[N + 100];

int pref(int i){
	int sum = 0;
	for(; i > 0; i-= i & -i){
		sum+= t[i];
	}
	return sum;
}

void add(int i, int x){
	int pos = i;
	for(; i <= n; i+= i & -i){
		t[i]+= x;
	}
}
int sum(int l, int r){
	return pref(r) - pref(l-1);
}
long long query(int a, int b){
	long long ans = 0;
	while(chain[b] != chain[a]){
		ans+= sum(pos[chain[b]], pos[b]);
		b = up[chain[b]][0];
	}
	ans+= sum(pos[a], pos[b]);
	return ans;
}
long long dp[N+10][2];
vector<vector<array<int, 3> > > transit(N+10);
int last[N+10];
void calc(int v, int par){
	long long sum1 = 0;
	for(int to : g[v]){
		if(to == par) continue;
		calc(to, v);
		sum1+= max(dp[to][0], dp[to][1]);
	}
	dp[v][0] = max(dp[v][0], sum1);
	dp[v][1] = max(dp[v][1], sum1);
	for(auto &[a, b, c] : transit[v]){
		long long sumA = query(v, a) + query(v, b) + dp[v][1] + c;
		long long sumB = dp[v][1]; 
		sumA-= dp[v][0];
		sumA = sumA + dp[v][0] - dp[v][1] + dp[v][0] - dp[v][1];
		if(dp[v][1] < sumA + sumB){
			dp[v][1] = max(dp[v][1], sumA + sumB);
		}
	}	
	add(pos[v], (dp[v][0] - dp[v][1]) - last[pos[v]]);
	last[pos[v]] = dp[v][0] - dp[v][1];
}


signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	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);
	}
	int m; cin >> m;
	dfs(1, 1);
	for(auto i = 0;i < m; i++){
		int a, b, c;
		cin >> a >> b >> c;
		int lc = lca(a, b);
		transit[lc].push_back({a, b, c});
	}
	timer = 1;
	decompose(1, 1, 1);
	calc(1, 1);
	cout << dp[1][1] << '\n';
	
	
	return 0;
}

Compilation message (stderr)

election_campaign.cpp: In function 'void add(int, int)':
election_campaign.cpp:72:6: warning: unused variable 'pos' [-Wunused-variable]
   72 |  int pos = i;
      |      ^~~

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