제출 #1361613

#제출 시각아이디문제언어결과실행 시간메모리
1361613iamhereforfunElection Campaign (JOI15_election_campaign)C++20
100 / 100
347 ms41720 KiB
// Starcraft 2 enjoyer //

#include <bits/stdc++.h>

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

#define LSOne(X) ((X) & -(X))
#define int long long

const int N = 2e5 + 5;
const int M = 1 << 15;
const int B = 18;
const long long K = 2;
const int LG = 20;
const int INF = 1e9 + 5;
const int P = 31;
const int MOD = 1e9 + 7;
const int nx[] = {0, 1, 0, -1}, ny[] = {-1, 0, 1, 0};

struct Fenwick
{
    vector<int> ft;
    int n;
    Fenwick(int len)
    {
        n = len;
        ft.assign(n + 1, 0);
    }
    void update(int pos, int val)
    {
        while (pos <= n)
        {
            ft[pos] += val;
            pos += LSOne(pos);
        }
    }
    int get(int pos)
    {
        int sum = 0;
        while (pos > 0)
        {
            sum += ft[pos];
            pos -= LSOne(pos);
        }
        return sum;
    }
    int get(int l, int r)
    {
        return get(r) - get(l - 1);
    }
} ft(N);

int n, q, binlift[LG][N], depth[N], sum[N], in[N], out[N], id;
vector<int> adj[N];
vector<array<int, 3>> path[N];

void dfs1(int c, int p)
{
    in[c] = id++;
    for (int i : adj[c])
    {
        if (i == p)
            continue;
        depth[i] = depth[c] + 1;
        binlift[0][i] = c;
        for (int x = 1; x < LG; x++)
        {
            binlift[x][i] = binlift[x - 1][binlift[x - 1][i]];
        }
        dfs1(i, c);
    }
    out[c] = id - 1;
}

int lca(int a, int b)
{
    if (depth[a] != depth[b])
    {
        if (depth[a] < depth[b])
            swap(a, b);
        for (int x = 0; x < LG; x++)
        {
            if ((depth[a] - depth[b]) >> x & 1)
            {
                a = binlift[x][a];
            }
        }
    }
    if (a == b)
        return a;
    for (int x = LG - 1; x >= 0; x--)
    {
        if (binlift[x][a] != binlift[x][b])
        {
            a = binlift[x][a];
            b = binlift[x][b];
        }
    }
    return binlift[0][a];
}

int lift(int a, int b)
{
    for (int x = 0; x < LG; x++)
    {
        if (b >> x & 1)
            a = binlift[x][a];
    }
    return a;
}

void dfs2(int c, int p)
{
    int tot = 0;
    for (int i : adj[c])
    {
        if (i == p)
            continue;
        dfs2(i, c);
        tot += sum[i];
    }
    for (auto [a, b, w] : path[c])
    {
        // cout << a << " " << b << " " << w << "\n";
        if (a == c && b == c)
        {
            sum[c] = max(sum[c], tot + w);
        }
        else if (a == c)
        {
            int j = lift(b, -depth[c] + depth[b] - 1);
            sum[c] = max(sum[c], tot - sum[j] + w + ft.get(in[b]));
        }
        else if (b == c)
        {
            int j = lift(a, -depth[c] + depth[a] - 1);
            sum[c] = max(sum[c], tot - sum[j] + w + ft.get(in[a]));
        }
        else
        {
            int j = lift(a, -depth[c] + depth[a] - 1);
            int i = lift(b, -depth[c] + depth[b] - 1);
            // cout << i << " " << j << "BRUH\n";
            sum[c] = max(sum[c], tot - sum[j] - sum[i] + w + ft.get(in[a]) + ft.get(in[b]));
        }
    }
    sum[c] = max(sum[c], tot);
    for (int i : adj[c])
    {
        if (i == p)
            continue;
        ft.update(in[i], tot - sum[i]);
        ft.update(out[i] + 1, -(tot - sum[i]));
    }
    ft.update(in[c], tot);
    ft.update(in[c] + 1, -tot);
    // cout << tot << " " << sum[c] << " " << c << "\n";
}

inline void solve()
{
    cin >> n;
    for (int x = 0; x < n - 1; x++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    id = 1;
    dfs1(1, 0);
    cin >> q;
    for (int x = 0; x < q; x++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        path[lca(a, b)].push_back({a, b, w});
    }
    dfs2(1, 0);
    cout << sum[1] << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…