Submission #441190

#	Time	Username	Problem	Language	Result	Execution time	Memory
441190		JovanB	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	265 ms	31672 KiB

election_campaign

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

using ll = long long;
using ld = long double;

const int MAXN = 100000;
const int MXLOG = 18;

vector <int> graf[MAXN+5];
int dp[MAXN+5];
int par[MAXN+5][MXLOG+1];

int tjm;

int in[MAXN+5];
int out[MAXN+5];

int bit[2*MAXN+5];
int niz[2*MAXN+5];

void upd(int x, int val){
    while(x <= 2*MAXN){
        bit[x] += val;
        x += x & -x;
    }
}

int bitget(int x){
    int res = 0;
    while(x){
        res += bit[x];
        x -= x & -x;
    }
    return res;
}

int query(int l, int r){
    return bitget(r) - bitget(l-1);
}

void dfs_calc(int v, int p){
    in[v] = ++tjm;
    par[v][0] = p;
    for(int j=1; j<=MXLOG; j++) par[v][j] = par[par[v][j-1]][j-1];
    for(auto c : graf[v]) if(c != p) dfs_calc(c, v);
    out[v] = ++tjm;
}

bool is_parent(int a, int b){
    return (a == 0) || (in[a] <= in[b] && out[b] <= out[a]);
}

int lca(int a, int b){
    if(is_parent(a, b)) return a;
    for(int j=MXLOG; j>=0; j--) if(!is_parent(par[a][j], b)) a = par[a][j];
    return par[a][0];
}

struct Option{
    int a, b, c;
};

vector <Option> options[MAXN+5];

int prvidole(int a, int b){
    for(int j=MXLOG; j>=0; j--) if(!is_parent(par[b][j], a)) b = par[b][j];
    return b;
}

void dfs_solve(int v, int p){
    for(auto c : graf[v]){
        if(c != p){
            dfs_solve(c, v);
            dp[v] += dp[c];
        }
    }
    for(auto option : options[v]){
        int a = option.a;
        int b = option.b;
        int c = option.c;
        int val = c;
        if(is_parent(b, a)) swap(a, b);
        if(a == v){
            val += query(in[v], in[b]);
        }
        else{
            val += query(in[v], in[a]);
            int k = prvidole(v, b);
            val += query(in[k], in[b]);
        }
        dp[v] = max(dp[v], val);
    }
    if(v != 1){
        upd(in[p], dp[v]);
        upd(in[v], -dp[v]);
        upd(out[v], dp[v]);
        upd(out[p], -dp[v]);
    }
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n;
    for(int i=1; i<n; i++){
        int a, b;
        cin >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    dfs_calc(1, 0);
    int m;
    cin >> m;
    while(m--){
        int a, b, c;
        cin >> a >> b >> c;
        options[lca(a, b)].push_back({a, b, c});
    }
    dfs_solve(1, 0);
    cout << dp[1] << "\n";
    return 0;
}

/*
7
1 2
2 3
3 4
1 5
5 6
6 7
3
3 4 1
6 7 1
2 5 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