Submission #1355423

#TimeUsernameProblemLanguageResultExecution timeMemory
1355423tsetsenbilegElection Campaign (JOI15_election_campaign)C++20
100 / 100
207 ms49836 KiB
#include <bits/stdc++.h>
#define int long long
using ld = long double;
#define pr pair<int, int>
#define pb push_back
using namespace std;
const int INF = 1e18+1, MOD = 1e9+7, MAXN = 4e5+5, MAXA = 3106;

struct segtree{
    int n;
    vector<int> st;
    void init(int N) {
        n = N;
        st.resize(n * 4);
    }
    int L(int i) {return i << 1;}
    int R(int i) {return i << 1 | 1;}
    void pull(int i) {
        st[i] = st[L(i)] + st[R(i)];
    }
    void update(int pos, int val) {update(1, 1, n, pos, val);}
    void update(int i, int l, int r, int pos, int val) {
        if (l == r) {
            // CHECK THIS v
            st[i] = val;
            return;
        }
        int m = (l + r) >> 1;
        if (pos <= m) update(L(i), l, m, pos, val);
        else update(R(i), m+1, r, pos, val);
        pull(i);
    }
    int query(int ll, int rr) {return query(1, 1, n, ll, rr);}
    int query(int i, int l, int r, int ll, int rr) {
        if (ll > r || rr < l) return 0;
        if (ll <= l && r <= rr) return st[i];
        int m = (l + r) >> 1;
        int res = 0;
        res += query(L(i), l, m, ll, rr);
        res += query(R(i), m+1, r, ll, rr);
        return res;
    }
};

struct HLD{
    int n, chain, t;
    vector<vector<int>> edge;
    vector<int> w, order, root, pos, p;
    segtree dp0, dp1;
    void init(int N, const vector<vector<int>>& ed) {
        chain = 1;
        t = 1;
        edge = ed;
        n = N;
        dp0.init(n);
        dp1.init(n);
        w.resize(n+1); order.resize(n+1);
        root.resize(n+1); pos.resize(n+1); p.resize(n+1);
        dfs1(1, 0);
        dfs2(1, 0, 1);
    }
    int dfs1(int node, int par) {
        int res = 1;
        for (auto next : edge[node]) {
            if (next == par) continue;
            res += dfs1(next, node);
        }
        return w[node] = res;
    }
    void dfs2(int node, int par, int rooter) {
        int we = 0, heavy = -1;
        p[node] = par;
        order[node] = chain;
        root[node] = rooter;
        pos[node] = t++;
        for (auto next : edge[node]) {
            if (next == par) continue;
            if (w[next] > we) {
                we = w[next];
                heavy = next;
            }
        }
        if (heavy == -1) {
            return;
        }
        dfs2(heavy, node, rooter);
        for (auto next : edge[node]) {
            if (heavy == next || par == next) continue;
            chain++;
            dfs2(next, node, next);
        }
    }
    int lca(int a, int b) {
        while (order[a] != order[b]) {
            if (order[a] < order[b]) swap(a, b);
            a = p[root[a]];
        }
        if (pos[a] > pos[b]) swap(a, b);
        return a;
    }
    void update0(int x, int val) {
        dp0.update(pos[x], val);
    }
    void update1(int x, int val) {
        dp1.update(pos[x], val);
    }
    int add(int a, int b, int s) {
        int sum = 0;
        while (order[a] != order[b]) {
            if (order[a] < order[b]) swap(a, b);
            sum += dp0.query(pos[root[a]], pos[a]);
            sum -= dp1.query(pos[root[a]], pos[a]);
            a = p[root[a]];
        }
        if (pos[a] > pos[b]) swap(a, b);
        sum += dp0.query(pos[a], pos[b]);
        if (a != b) {
            sum -= dp1.query(pos[a]+1, pos[b]);
        }
        return sum + s;
    }
} hld;

vector<array<int, 3>> path;
vector<vector<int>> edge, lca;

int dfs(int node, int par) {
    int child = 0;
    for (auto next : edge[node]) {
        if (next == par) continue;
        child += dfs(next, node);
    }
    hld.update0(node, child);
    int mx = child;
    for (auto i : lca[node]) {
        auto& [x, y, s] = path[i];
        // cout << node << ' ' << y << '\n';
        int temp = hld.add(x, y, s);
        // cout << temp << ' ';
        mx = max(mx, temp);
    }
    hld.update1(node, mx);
    return mx;
}

void solve() {
    int n;
    cin >> n;
    edge.resize(n+1);
    for (int i = 0; i < n-1; i++) {
        int x, y;
        cin >> x >> y;
        edge[x].pb(y);
        edge[y].pb(x);
    }
    int m;
    cin >> m;
    hld.init(n, edge);
    path.resize(m);
    lca.resize(n+1);
    for (int i = 0; i < m; i++) {
        auto& [x, y, s] = path[i];
        cin >> x >> y >> s;
        lca[hld.lca(x, y)].pb(i);
    }
    cout << dfs(1, 0);
    // cout << '\n';
    // for (int i = 1; i <= n; i++) {
    //     cout << hld.dp0.query(i, i) << ' ';
    // }
    // cout << hld.dp1.query(1, 1);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    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...