Submission #1351708

#TimeUsernameProblemLanguageResultExecution timeMemory
1351708nguyenkhangninh99Election Campaign (JOI15_election_campaign)C++20
100 / 100
87 ms36064 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int maxn = 1e5 + 5, lg = 18;

int up[maxn][lg], dp[maxn], tot[maxn], bit[maxn];
int tin[maxn], out[maxn], timedfs;
vector<array<int, 3>> path[maxn];
vector<int> adj[maxn];

void update(int p, int v){
    for (; p < maxn; p += p & -p) bit[p] += v;
}
int query(int p){
    int res = 0;
    for (; p; p -= p & -p) res += bit[p];
    return res;
}

void dfs(int u, int p){
    tin[u] = ++timedfs;
    up[u][0] = p;
    for(int i = 1; i < lg; i++) up[u][i] = up[up[u][i - 1]][i - 1];
    for(int v: adj[u]) if(v != p) dfs(v, u);
    out[u] = timedfs;
}

bool inside(int u, int v){
    return tin[u] <= tin[v] && out[v] <= out[u];
}
int lca(int u, int v){
    if(inside(u, v)) return u;
    if(inside(v, u)) return v;
    for(int i = lg - 1; i >= 0; i--){
        if(!inside(up[u][i], v)) u = up[u][i];
    }
    return up[u][0];
}

void calc(int u, int p){
    for(int v : adj[u]){
        if(v != p){
            calc(v, u);
            tot[u] += dp[v];
        }
    }

    dp[u] = tot[u];

    for(auto [a, b, c]: path[u]){
        dp[u] = max(dp[u], c + tot[u] + query(tin[a]) + query(tin[b]));
    }
    update(tin[u], tot[u] - dp[u]);
    update(out[u] + 1, -(tot[u] - dp[u]));
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n; cin >> n;
    for(int i = 1; i <= n - 1; i++){ 
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, 1);
    int m; cin >> m;
    for(int i = 1; i <= m; i++){
        int u, v, w; cin >> u >> v >> w;
        path[lca(u, v)].push_back({u, v, w});
    }
    calc(1, 1);
    cout << dp[1];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...