Submission #1150011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150011		andrewp	Election Campaign (JOI15_election_campaign)	C++20	10 / 100	95 ms	72560 KiB

election_campaign

//Dedicated to my love, ivaziva
#include <bits/stdc++.h> 
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(a) ((int)a.size()) 
const int N=1e6+5;   

struct node {
    int a, b, c, pa, pb;
};  

int n, m, up[N][20], dep[N]; 
vector<int> g[N]; 
ll dp[N][2]; 
vector<node> pom[N];

void dfs(int x, int p) {
    dep[x]=dep[p]+1;
    up[x][0]=p;
    for (int i=1; i<20; i++) 
        up[x][i]=up[up[x][i-1]][i-1]; 
    for (int u:g[x]) {
        if (u!=p) 
            dfs(u, x);
    }
} 

int raise(int x, int y) {
    int z=0;
    while (y) {
        if (y&1) 
            x=up[x][z];
        z++;
        y>>=1;
    }
    return x;
}

array<int, 3> lca(int a, int b) {
    if (dep[a]>dep[b]) 
        swap(a, b);
    int x=dep[b]-dep[a];
    int ob=b; 
    b=raise(b, x);
    if (a==b) 
        return {a, raise(ob, x-1), -1};
    for (int i=19; i>=0; i--) {
        if (up[a][i]!=up[b][i]) {
            a=up[a][i];
            b=up[b][i];
        }
    } 
    return {up[a][0], a, b}; 
}

void dfs2(int x, int p) {  
    ll chsum=0; 
    for (int u:g[x]) {
        if (u!=p) {
            dfs2(u, x); 
            chsum+=max(dp[u][0], dp[u][1]); 
        }
    } 
    dp[x][0]=chsum;  
    for (node nd:pom[x]) { 
        if (nd.pb==-1) { 
            dp[x][1]=max(dp[x][1], nd.c+(chsum-max(dp[nd.pa][0], dp[nd.pa][1])+dp[dep[nd.a]>dep[nd.b]?nd.a:nd.b][0])); 
        }
        else { 
            dp[x][1]=max(dp[x][1], nd.c+(chsum-max(dp[nd.pa][0], dp[nd.pa][1])-max(dp[nd.pb][0], dp[nd.pb][1])+
                dp[nd.a][0]+dp[nd.b][0])); 
        }
    }
}

int main () {
    ios::sync_with_stdio(false), cin.tie(0);
        
    cin >> n;
    for (int i=1; i<n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1, 0);  
    int q;
    cin >> q;
    while (q--) {
        int a, b, c;
        cin >> a >> b >> c; 
        array<int, 3> LCA=lca(a, b);    
        pom[LCA[0]].pb({a, b, c, LCA[1], LCA[2]});
    } 
    dfs2(1, 0);       
    cout << max(dp[1][0], dp[1][1]) << '\n'; 
}   

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