Submission #1355369

#TimeUsernameProblemLanguageResultExecution timeMemory
1355369kawhietElection Campaign (JOI15_election_campaign)C++20
10 / 100
65 ms27496 KiB
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 47
#endif

constexpr int N = 1e5;

vector<int> g[N];
vector<array<int, 3>> t[N];

int to[N][20], lvl[N], dp[N], in[N], out[N];

int timer = 0;

void init(int u, int p) {
    in[u] = timer++;
    to[u][0] = p;
    for (int i = 1; i < 20; i++) {
        to[u][i] = to[to[u][i - 1]][i - 1];
    }
    for (auto v : g[u]) {
        if (v != p) {
            lvl[v] = lvl[u] + 1;
            init(v, u);
        }
    }
    out[u] = timer - 1;
}

int lca(int x, int y) {
    if (lvl[x] < lvl[y]) {
        swap(x, y);
    }
    int d = lvl[x] - lvl[y];
    for (int i = 0; i < 20; i++) {
        if (d & (1 << i)) {
            x = to[x][i];
        }
    }
    if (x == y) {
        return x;
    }
    for (int i = 19; i >= 0; i--) {
        if (to[x][i] != to[y][i]) {
            x = to[x][i];
            y = to[y][i];
        }
    }
    return to[x][0];
}

void dfs(int u, int p) {
    int s = 0;
    for (auto v : g[u]) {
        if (v == p) continue;
        dfs(v, u);
        s += dp[v];
    }
    dp[u] = s;
    for (auto [a, b, c] : t[u]) {
        int cur = s + c;
        if (a != u) {
            for (auto x : g[u]) {
                if (x == p) continue;
                if (in[x] <= in[a] && out[a] <= out[x]) {
                    cur -= dp[x];
                }
            }
            for (auto x : g[a]) {
                if (x == to[a][0]) continue;
                cur += dp[x];
            }
        }
        if (b != u) {
            for (auto x : g[u]) {
                if (x == p) continue;
                if (in[x] <= in[b] && out[b] <= out[x]) {
                    cur -= dp[x];
                }
            }
            for (auto x : g[b]) {
                if (x == to[b][0]) continue;
                cur += dp[x];
            }
        }
        dp[u] = max(dp[u], cur);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    init(0, 0);
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        t[lca(a, b)].push_back({a, b, c});
    }
    dfs(0, 0);
    cout << dp[0] << '\n';
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...