Submission #1264520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264520		namhh	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	143 ms	29912 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e5+1;
const int lg = 17;
int n,m,t[N][lg],h[N],dp[N][2],sta[N],pos[N],ed[N],bits[N],timer = 1;
struct query{
	int u,v,c;
};
query qr[N];
vector<query>aqua[N];
vector<int>adj[N];
void update(int u, int val){
	while(u <= n){
		bits[u] += val;
		u += u & (-u);
	}
}
int query(int u){
	int sum = 0;
	while(u > 0){
		sum += bits[u];
		u -= u & (-u);
	}
	return sum;
}
void dfs(int u, int p){ 
    h[u] = h[p]+1;
    t[u][0] = p;
    for(int i = 1; i <= 16; i++) t[u][i] = t[t[u][i-1]][i-1];
    for(int v : adj[u]){
        if(v == p) continue;
        dfs(v,u);
    } 
}
void dfs1(int u, int p){
	sta[u] = timer;
	pos[timer] = u;
	timer++;
	for(int v: adj[u]){
		if(v != p) dfs1(v,u);
	}
	ed[u] = timer-1;
}
int lca(int u, int v){ 
    if(h[u] < h[v]) swap(u,v); 
    for(int i = 16; i >= 0; i--)
        if(h[t[u][i]] >= h[v]) u = t[u][i];
    if(u == v) return u; 
    for(int i = 16; i >= 0; i--)
        if(t[u][i] != t[v][i]){
            u = t[u][i];
            v = t[v][i];
        }
    return t[u][0];
}
int jump(int v, int u){
	for(int i = 16; i >= 0; i--){
		if(h[t[v][i]] > h[u]) v = t[v][i];
	}
	return v;
}
void dfsdp(int u, int p){
	int sum = 0;
	for(int v: adj[u]){
		if(v != p){
			dfsdp(v,u);
			sum += max(dp[v][0],dp[v][1]);
		}
	}
	dp[u][0] = sum;
	if(!aqua[u].empty()){
	    int mmb = -1e9;
	    for(auto v: aqua[u]){
	    	int aqua = v.c;
		    if(v.u != u){
		    	int t = jump(v.u,u);
		    	aqua += query(sta[v.u])-query(sta[t])+dp[t][0]-max(dp[t][0],dp[t][1]);
			}
			if(v.v != u){
		    	int t = jump(v.v,u);
		    	aqua += query(sta[v.v])-query(sta[t])+dp[t][0]-max(dp[t][0],dp[t][1]);
			}
			mmb = max(mmb,aqua);
	    }
	    dp[u][1] = sum+mmb;
	    update(sta[u],dp[u][0]-max(dp[u][0],dp[u][1]));
	    update(ed[u]+1,max(dp[u][0],dp[u][1])-dp[u][0]);
	}
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for(int i = 1; i < n; i++){
		int u,v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1,0);
	dfs1(1,0);
	cin >> m;
	for(int i = 1; i <= m; i++){
		cin >> qr[i].u >> qr[i].v >> qr[i].c;
		int k = lca(qr[i].u,qr[i].v);
		aqua[k].push_back(qr[i]);
	}
	dfsdp(1,0);
//	for(int i = 1; i <= n; i++){
//		for(int j = 0; j <= 1; j++) cout << i << " " << j << " " << dp[i][j] << "\n";
//	}
    cout << max(dp[1][0],dp[1][1]);
}

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