Submission #1168080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168080		cpismylifeOwO	Election Campaign (JOI15_election_campaign)	C++20	30 / 100	1099 ms	95632 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;

struct Road
{
    int u, v, lca;
    long long w;
};

int n, m;
vector<int> graph[MaxN];
Road arr[MaxN];

void Inp()
{
    cin >> n;
    for (int x = 1; x < n; x++)
    {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    cin >> m;
    for (int x = 1; x <= m; x++)
    {
        cin >> arr[x].u >> arr[x].v >> arr[x].w;
    }
}

int h[MaxN];
int par[MaxN];
int sz[MaxN];
int nxt[MaxN];

void PreDFS(int u, int p)
{
    sz[u] = 1;
    nxt[u] = -1;
    for (int x : graph[u])
    {
        if (x != p)
        {
            h[x] = h[u] + 1;
            par[x] = u;
            PreDFS(x, u);
            sz[u] = sz[x] + 1;
            if (nxt[u] == -1 || sz[nxt[u]] < sz[x])
            {
                nxt[u] = x;
            }
        }
    }
}

int curChain, curPos;
int ChainHead[MaxN];
int ChainID[MaxN];
int Pos[MaxN];
int Arr[MaxN];

void HLD(int u, int p)
{
    //cout << u << endl;
    if (ChainHead[curChain] == 0)
    {
        ChainHead[curChain] = u;
    }
    ChainID[u] = curChain;
    curPos++;
    Pos[u] = curPos;
    Arr[curPos] = u;
    if (nxt[u] != -1)
    {
        HLD(nxt[u], u);
    }
    for (int x : graph[u])
    {
        if (x != nxt[u] && x != p)
        {
            curChain++;
            HLD(x, u);
        }
    }
}

int LCA(int u, int v)
{
    while (ChainID[u] != ChainID[v])
    {
        if (ChainID[u] < ChainID[v])
        {
            v = par[ChainHead[ChainID[v]]];
        }
        else
        {
            u = par[ChainHead[ChainID[u]]];
        }
    }
    if (h[u] < h[v])
    {
        return u;
    }
    return v;
}

long long SegTree[4 * MaxN];
long long F[MaxN];
long long sumChild[MaxN];

void Update(int id, int l, int r, int u, long long v)
{
    if (u < l || r < u)
    {
        return;
    }
    if (l == r)
    {
        SegTree[id] = v;
        return;
    }
    int mid = (l + r) >> 1;
    Update(id << 1, l, mid, u, v);
    Update(id << 1 | 1, mid + 1, r, u, v);
    SegTree[id] = (SegTree[id << 1] + SegTree[id << 1 | 1]);
}

long long Get(int id, int l, int r, int i, int j)
{
    if (j < l || r < i)
    {
        return 0;
    }
    if (i <= l && r <= j)
    {
        return SegTree[id];
    }
    int mid = (l + r) >> 1;
    return (Get(id << 1, l, mid, i, j) + Get(id << 1 | 1, mid + 1, r, i, j));
}

void UpdatePath(int u)
{
    if (u > 1)
    {
        int p = par[u];
        if (nxt[p] != u)
        {
            sumChild[p] += F[u];
        }
        Update(1, 1, n, Pos[p], sumChild[p]);
    }
}

long long GetPath(int u, int v, int lca, long long curs)
{
    long long res = 0;
    if (nxt[u] != -1)
    {
        res += F[nxt[u]];
    }
    while (ChainID[u] > ChainID[lca])
    {
        res += Get(1, 1, n, Pos[ChainHead[ChainID[u]]], Pos[u]);
        u = ChainHead[ChainID[u]];
        res -= F[u];
        u = par[u];
        if (nxt[u] != -1)
        {
            res += F[nxt[u]];
        }
    }
    res += Get(1, 1, n, Pos[lca], Pos[u]);
    if (nxt[v] != -1)
    {
        res += F[nxt[v]];
    }
    while (ChainID[v] > ChainID[lca])
    {
        res += Get(1, 1, n, Pos[ChainHead[ChainID[v]]], Pos[v]);
        v = ChainHead[ChainID[v]];
        res -= F[v];
        v = par[v];
        if (nxt[v] != -1)
        {
            res += F[nxt[v]];
        }
    }
    res += Get(1, 1, n, Pos[lca], Pos[v]);
    res -= curs;
    return res;
}

vector<int> mark[MaxN];
vector<int> curh[MaxN];

void Exc()
{
    PreDFS(1, -1);
    curChain = 0;
    curPos = 1;
    HLD(1, -1);
    for (int x = 1; x <= m; x++)
    {
        arr[x].lca = LCA(arr[x].u, arr[x].v);
        mark[arr[x].lca].push_back(x);
    }
    for (int x = 1; x <= n; x++)
    {
        curh[h[x]].push_back(x);
    }
    for (int x = n; x >= 0; x--)
    {
        for (int u : curh[x])
        {
            long long curs = 0;
            curs = sumChild[u];
            if (nxt[u] != -1)
            {
                curs += F[nxt[u]];
            }
            F[u] = curs;
            for (int y : mark[u])
            {
                F[u] = max(F[u], GetPath(arr[y].u, arr[y].v, arr[y].lca, curs) + arr[y].w);
            }
            UpdatePath(u);
        }
    }
    cout << F[1];
}

int main()
{
    //freopen("A.INP", "r", stdin);
    //freopen("A.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int w = 1; w <= test; w++)
    {
        Inp();
        Exc();
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 0 / 30
• Subtask 5: 10 / 10
• Subtask 6: 0 / 40