Submission #879007

#	Time	Username	Problem	Language	Result	Execution time	Memory
879007		hafo	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	113 ms	28756 KiB

election_campaign

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 17;
const int maxn = 1e5 + 7;
const ll oo = 1e9 + 69;

int n, m, u, v, c, dp[maxn], sum[maxn], st[maxn], en[maxn], timer = 0;
vector<int> g[maxn], ev[maxn];
struct query {
    int u, v, c;
} que[maxn];

struct LCA {
    int p[LOG][maxn], dep[maxn];

    void dfs(int u, int par) {
        p[0][u] = par;
        for(auto v:g[u]) {
            if(v == par) continue;
            dep[v] = dep[u] + 1;
            dfs(v, u);
        }
    }

    int get_lca(int u, int v) {
        if(dep[u] < dep[v]) swap(u, v);
        int k = dep[u] - dep[v];
        for(int i = 0; i < LOG; i++)
            if((k >> i) & 1) u = p[i][u];
        if(u == v) return u;
        for(int i = LOG - 1; i >= 0; i--)
        if(p[i][u] != p[i][v]) {
            u = p[i][u];
            v = p[i][v];
        }
        return p[0][u];
    }

    int jump(int u, int k) {
        for(int i = 0; i < LOG; i++) 
            if((k >> i) & 1) u = p[i][u];
        return u;
    }

    void init() {
        dep[1] = 0;
        dfs(1, 0);
        for(int i = 1; i < LOG; i++) {
            for(int u = 1; u <= n; u++) p[i][u] = p[i - 1][p[i - 1][u]];
        }
    }

} lca;

void dfs_st(int u, int par) {
    st[u] = ++timer;
    for(auto v:g[u]) {
        if(v == par) continue;
        dfs_st(v, u);
    }
    en[u] = timer;
} 

struct BIT {
    int bit[maxn];

    void update(int x, int val) {
        for(; x <= n; x += x&-x) bit[x] += val;
    }
    
    int get(int x) {
        int ans = 0;
        for(; x; x -= x&-x) ans += bit[x];
        return ans;
    }

} bit;

int trace(int v, int u) {
    int res = 0;
    while(v != u) {
        res += dp[v] - sum[v];
        v = lca.p[0][v];
    }
    return res;
}

void dfs(int u, int par) {
    for(auto v:g[u]) {
        if(v == par) continue;
        dfs(v, u);
        sum[u] += dp[v];
    }

    maxi(dp[u], sum[u]);
    for(auto i:ev[u]) {
        int tot = bit.get(st[que[i].u]) + bit.get(st[que[i].v]);
        // if(que[i].u != u) tot += trace(que[i].u, u);
        // if(que[i].v != u) tot += trace(que[i].v, u);
        maxi(dp[u], sum[u] - tot + que[i].c);
    }
    bit.update(st[u], dp[u] - sum[u]);
    bit.update(en[u] + 1, -dp[u] + sum[u]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n;
    for(int i = 1; i < n; i++) {
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }

    lca.init();
    dfs_st(1, 0);

    cin>>m;
    for(int i = 1; i <= m; i++) {
        cin>>que[i].u>>que[i].v>>que[i].c;
        ev[lca.get_lca(que[i].u, que[i].v)].pb(i);
    }
    dfs(1, 0);
    cout<<dp[1];
    return 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