Submission #361576

#	Time	Username	Problem	Language	Result	Execution time	Memory
361576		RyoPham	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	373 ms	34520 KiB

election_campaign

#define taskname "test"

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second

typedef long long lli;
typedef pair<int, int> pii;

const int maxn = 1e5 + 5;
const int logn = 17;

int n, m;
vector<int> gr[maxn];
int a[maxn], b[maxn], c[maxn];

int depth[maxn], p[maxn][logn];

vector<int> paths_id[maxn];

int total_child[maxn], dp[maxn];

struct fenwick
{
    int val[maxn];

    void update(int x, int k)
    {
        for(; x < maxn; x += x & -x)
            val[x] += k;
    }

    int get(int x)
    {
        int res = 0;
        for(; x > 0; x -= x & -x)
            res += val[x];
        return res;
    }

    int get(int l, int r)
    {
        return get(r) - get(l - 1);
    }
};

struct hld
{
    int sub[maxn], heavy[maxn], p[maxn];
    int nchain, ntime;
    int chain_head[maxn], chain_id[maxn], pos[maxn];
    fenwick tree;

    void dfs_pre(int u)
    {
        sub[u] = 1;
        heavy[u] = -1;
        for(auto&v: gr[u])
        {
            p[v] = u;
            dfs_pre(v);
            sub[u] += sub[v];
            if(heavy[u] == -1 || sub[v] > sub[heavy[u]])
                heavy[u] = v;
        }
    }

    void dfs_decompose(int u)
    {
        if(chain_head[nchain] == 0)
            chain_head[nchain] = u;
        chain_id[u] = nchain;
        pos[u] = ++ntime;

        if(heavy[u] != -1)
            dfs_decompose(heavy[u]);

        for(auto&v: gr[u])
            if(v != heavy[u])
            {
                ++nchain;
                dfs_decompose(v);
            }
    }

    void decompose()
    {
        dfs_pre(1);
        dfs_decompose(1);
    }

    void update(int u, int k)
    {
        if(p[u] == 0 || heavy[p[u]] == u) return;
        tree.update(pos[p[u]], k);
    }

    int get(int u, int a)
    {
        int a_chain = chain_id[a], u_chain = chain_id[u];
        int res = 0;
        if(heavy[u]) res += dp[heavy[u]];
        while(true)
        {
            if(u_chain == a_chain)
            {
                res += tree.get(pos[a], pos[u]);
                break;
            }
            res += tree.get(pos[chain_head[u_chain]], pos[u]);
            res -= dp[chain_head[u_chain]];
            res += dp[heavy[p[chain_head[u_chain]]]];
            u = p[chain_head[u_chain]];
            u_chain = chain_id[u];
        }
        return res;
    }
} data;

void read_input()
{
    cin >> n;
    for(int i = 1; i < n; ++i)
    {
        int u, v;
        cin >> u >> v;
        gr[u].push_back(v);
        gr[v].push_back(u);
    }
    cin >> m;
    for(int i = 1; i <= m; ++i)
        cin >> a[i] >> b[i] >> c[i];
}

void dfs_modify(int u, int par)
{
    depth[u] = depth[par] + 1;
    p[u][0] = par;
    for(int k = 1; k < logn; ++k)
        p[u][k] = p[p[u][k - 1]][k - 1];
    vector<int> childs;
    for(auto&v: gr[u])
        if(v != par)
        {
            childs.push_back(v);
            dfs_modify(v, u);
        }
    gr[u] = childs;
}

int lca(int u, int v)
{
    if(depth[u] < depth[v]) swap(u, v);
    for(int k = logn - 1; k >= 0; --k)
        if(depth[p[u][k]] >= depth[v])
            u = p[u][k];
    if(u == v) return u;
    for(int k = logn - 1; k >= 0; --k)
        if(p[u][k] != p[v][k])
        {
            u = p[u][k];
            v = p[v][k];
        }
    return p[u][0];
}

int jump(int u, int dist)
{
    for(int k = 0; k < logn; ++k)
        if(dist >> k & 1) u = p[u][k];
    return u;
}

void init()
{
    dfs_modify(1, 0);
    for(int i = 1; i <= m; ++i)
        paths_id[lca(a[i], b[i])].push_back(i);
    data.decompose();
}

void dfs_solve(int u)
{
    for(auto&v: gr[u])
    {
        dfs_solve(v);
        total_child[u] += dp[v];
    }

    dp[u] = total_child[u];
    for(auto&id: paths_id[u])
    {
        int x = a[id], y = b[id], cost = c[id];
        int tx, ty;
        if(x == u)
        {
            ty = jump(y, depth[y] - depth[u] - 1);
            dp[u] = max(dp[u], data.get(y, ty) + total_child[u] - dp[ty] + cost);
        }
        else if(y == u)
        {
            tx = jump(x, depth[x] - depth[u] - 1);
            dp[u] = max(dp[u], data.get(x, tx) + total_child[u] - dp[tx] + cost);
        }
        else
        {
            tx = jump(x, depth[x] - depth[u] - 1);
            ty = jump(y, depth[y] - depth[u] - 1);
            dp[u] = max(dp[u], data.get(x, tx) + data.get(y, ty) + total_child[u] - dp[tx] - dp[ty] + cost);
        }
    }
    data.update(u, dp[u]);
}

void solve()
{
    dfs_solve(1);
    cout << dp[1] << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read_input();
    init();
    solve();
}

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