Submission #931857

#	Time	Username	Problem	Language	Result	Execution time	Memory
931857		parlimoos	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	134 ms	38084 KiB

election_campaign

//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

int n , m;
vector<int> tr[100000];
int times[100000][2] , bl[100000][20];
int seg[400001][3] , is[100000];
int dp[100000];
vector<arr(3)> pths[100000];

void buildSeg(int l = 0 , int r = n - 1 , int i = 1){
	seg[i][0] = l , seg[i][1] = r;
	if(l == r) is[l] = i;
	else{
		int c = (l + r - 1) >>  1;
		buildSeg(l , c , i << 1) , buildSeg(c + 1 , r , (i << 1) | 1);
	}
}
void updSeg(int l , int r , int i , int val){
	if(seg[i][0] >= l and seg[i][1] <= r) seg[i][2] += val;
	else if(seg[i][1] >= l and seg[i][0] <= r) updSeg(l , r , i << 1 , val) , updSeg(l , r , (i << 1) | 1 , val);
}
int getSeg(int i){
	int res = seg[i][2];
	while(i > 1) i >>= 1 , res += seg[i][2];
	return res;
}
int timer = -1;
void dfs1(int v = 0 , int p = -1){
	times[v][0] = ++timer;
	bl[v][0] = p;
	for(int i = 1 ; i < 20 ; i++){
		if(bl[v][i - 1] == -1) bl[v][i] = -1;
		else bl[v][i] = bl[bl[v][i - 1]][i - 1];
	}
	for(int u : tr[v]) if(u != p) dfs1(u , v);
	times[v][1] = timer;
}
int lca(int v1 , int v2){
	if(times[v1][0] <= times[v2][0] and times[v1][1] >= times[v2][0]) return v1;
	if(times[v2][0] <= times[v1][0] and times[v2][1] >= times[v1][0]) return v2;
	int u = v2;
	for(int i = 19 ; i >= 0 ; i--){
		if(bl[u][i] == -1) continue;
		if(times[bl[u][i]][0] <= times[v1][0] and times[bl[u][i]][1] >= times[v1][0]) continue;
		u = bl[u][i];
	}
	return bl[u][0];
}
void dfs2(int v = 0){
	int sz = 0;
	for(int u : tr[v]){
		if(u == bl[v][0]) continue;
		dfs2(u) , sz += dp[u];
	}
	updSeg(times[v][0] , times[v][0] , 1 , sz);
	for(int u : tr[v]){
		if(u == bl[v][0]) continue;
		updSeg(times[u][0] , times[u][1] , 1 , sz - dp[u]);
	}
	dp[v] = sz;
	for(auto pth : pths[v]){
		int u1 = pth[0] , u2 = pth[1] , c = pth[2];
		if(u1 == v and u2 == v) dp[v] = max(dp[v] , sz + c);
		else if(u1 == v) dp[v] = max(dp[v] , getSeg(is[times[u2][0]]) + c);
		else{
			int d = getSeg(is[times[u1][0]]) + getSeg(is[times[u2][0]]) - sz + c;
			dp[v] = max(dp[v] , d);
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for(int i = 1 ; i < n ; i++){
		int v , u;
		cin >> v >> u;
		v-- , u--;
		tr[v].pb(u) , tr[u].pb(v);
	}
	dfs1() , buildSeg();
	cin >> m;
	for(int i = 0 ; i < m ; i++){
		int v , u , c;
		cin >> v >> u >> c;
		v-- , u--;
		if(times[v][0] > times[u][0]) swap(v , u);
		int d = lca(v , u);
		pths[d].pb({v , u , c});
	}
	dfs2();
	cout << dp[0];
}

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