Submission #87221

#	Time	Username	Problem	Language	Result	Execution time	Memory
87221		tieunhi	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	297 ms	149804 KiB

election_campaign

#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define ll long long
#define mid (r + l)/2
#define N 100005
#define LN 19

using namespace std;

int n, numQ, tin[N], tout[N], tt, h[N], p[N][LN], dp[N];
vector<pair<pii, int> >q[N];
vector<int> a[N];

struct BIT
{
    int t[N];
    void upd(int x, int val)
    {
        for (; x < N; x += (x & -x)) t[x] += val;
    }
    void upd(int l, int r, int val)
    {
        upd(l, val);
        upd(r+1, -val);
    }
    int get(int x)
    {
        int ans = 0;
        for (; x; x -= (x & -x)) ans += t[x];
        return ans;
    }
}t;

void preDFS(int u)
{
    tin[u] = ++tt;
    for (auto v : a[u])
    {
        if (v == p[u][0]) continue;
        h[v] = h[u] + 1;
        p[v][0] = u;
        FOR(i, 1, LN-1) p[v][i] = p[p[v][i-1]][i-1];
        preDFS(v);
    }
    tout[u] = tt;
}
int LCA(int u, int v)
{
    if (h[u] > h[v]) swap(u, v);
    int delta = h[v] - h[u];
    FOR(i, 0, LN-1)
        if ((delta >> i) & 1) v = p[v][i];
    if (u == v) return u;
    FORD(i, LN-1, 0)
        if (p[u][i] != p[v][i])
        {
            u = p[u][i];
            v = p[v][i];
        }
    return p[u][0];
}
int DFS(int u)
{
    int cur = 0;
    for (auto v : a[u])
    {
        if (v == p[u][0]) continue;
        cur += DFS(v);
    }
    dp[u] = cur;
    for (auto z : q[u])
    {
        int uu = z.F.F;
        int vv = z.F.S;
        int ww = z.S;
        dp[u] = max(dp[u], ww + t.get(tin[uu]) + t.get(tin[vv]) + cur);
    }
    t.upd(tin[u], tout[u], cur - dp[u]);
    return dp[u];
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    cin >> n;
    FOR(i, 2, n)
    {
        int u, v; cin >> u >> v;
        a[u].PB(v);
        a[v].PB(u);
    }
    preDFS(1);
    cin >> numQ;
    FOR(i, 1, numQ)
    {
        int u, v, w; cin >> u >> v >> w;
        int lca = LCA(u, v);
        q[lca].PB(mp(mp(u, v), w));
    }
    cout <<DFS(1);
}

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