Submission #1355762

#TimeUsernameProblemLanguageResultExecution timeMemory
1355762kawhietElection Campaign (JOI15_election_campaign)C++20
0 / 100
130 ms19320 KiB
#include <bits/stdc++.h>
using namespace std;

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

struct HLD {
    int n, timer;
    vector<vector<int>> g;
    vector<int> sz, heavy, par, in, head;

    struct SegmentTree {
        int n;
        vector<int> t;

        void init(int _n) {
            n = _n;
            t.resize(4 * n);
        }

        int merge(int x, int y) {
            return x + y;
        }

        void update(int id, int tl, int tr, int i, int v) {
            if (tl == tr) {
                t[id] = v;
                return;
            }
            int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
            if (i <= tm) {
                update(x, tl, tm, i, v);
            } else {
                update(y, tm + 1, tr, i, v);
            }
            t[id] = merge(t[x], t[y]);
        }

        int get(int id, int tl, int tr, int l, int r) {
            if (r < tl || tr < l) return 0;
            if (l <= tl && tr <= r) return t[id];
            int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
            return merge(get(x, tl, tm, l, r), get(y, tm + 1, tr, l, r));
        }

        void update(int i, int v) { update(0, 0, n - 1, i, v); }
        int get(int l, int r) { return get(0, 0, n - 1, l, r); }
    } t;

    void init(int _n, vector<vector<int>> &_g) {
        n = _n;
        g = _g;
        sz.assign(n, 0);
        heavy.assign(n, -1);
        par.assign(n, -1);
        in.assign(n, 0);
        head.assign(n, 0);
        timer = 0; 
        dfs(0, -1);
        hld(0, 0);
        t.init(n);
    }

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

    void hld(int u, int h) {
        in[u] = timer++;
        head[u] = h;
        if (heavy[u] != -1) {
            hld(heavy[u], h);
        }
        for (auto v : g[u]) {
            if (v == par[u] || v == heavy[u]) continue;
            hld(v, v);
        }
    }

    int lca(int x, int y) {
        while (head[x] != head[y]) {
            if (in[head[x]] < in[head[y]]) swap(x, y);
            x = par[head[x]];
        }
        if (in[x] < in[y]) swap(x, y);
        return y;
    }

    int get(int x, int y) {
        int ret = 0;
        while (head[x] != head[y]) {
            if (in[head[x]] < in[head[y]]) swap(x, y);
            ret = t.merge(ret, t.get(in[head[x]], in[x]));
            x = par[head[x]];
        }
        if (in[x] < in[y]) swap(x, y);
        ret = t.merge(ret, t.get(in[y], in[x]));
        return ret;
    }

    void update(int u, int x) {
        t.update(in[u], x);
    }
};

vector<vector<int>> g;
vector<vector<array<int, 3>>> t;
vector<int> dp;

HLD hld;

void dfs(int u, int p) {
    int s = 0;
    for (auto v : g[u]) {
        if (v == p) continue;
        dfs(v, u);
        dp[u] += dp[v];
    }
    for (auto [a, b, c] : t[u]) {
        dp[u] = max(dp[u], hld.get(a, b) + c);
    }
    if (u == hld.head[u] && p != -1) {
        hld.update(p, dp[u]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    g.resize(n);
    dp.resize(n);
    t.resize(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);
    }
    hld.init(n, g);
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        t[hld.lca(a, b)].push_back({a, b, c});
    }
    dfs(0, -1);
    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...