Submission #102390

#	Time	Username	Problem	Language	Result	Execution time	Memory
102390		Alexa2001	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	416 ms	28800 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;

/// 17:03

const int Nmax = 1e5 + 5, lg = 18;
typedef long long ll;

int n, t[lg+2][Nmax], level[Nmax], In[Nmax], Out[Nmax], tmp;
ll sum[Nmax], dp[Nmax];

struct Plan
{
    int x, y, c;
};
vector<int> v[Nmax];
vector<Plan> plan[Nmax];



class AIB
{
    ll a[Nmax];
    int ub(int x) { return (x&(-x)); }

public:
    void update(int x, int y, ll val)
    {
        for(; x<=n; x+=ub(x)) a[x] += val;
        for(++y; y<=n; y+=ub(y)) a[y] -= val;
    }

    ll query(int x)
    {
        ll ans = 0;
        for(; x; x-=ub(x)) ans += a[x];
        return ans;
    }
} aib;


void dfs(int node)
{
    int i;
    for(i=1; i<=lg; ++i) t[i][node] = t[i-1][t[i-1][node]];

    In[node] = ++tmp;
    level[node] = level[t[0][node]] + 1;

    for(auto it : v[node])
        if(!level[it])
        {
            t[0][it] = node;
            dfs(it);
        }

    Out[node] = tmp;
}

int lca(int x, int y)
{
    if(level[x] < level[y]) swap(x, y);
    int up = level[x] - level[y], i;
    for(i=0; i<=lg; ++i)
        if(up & (1<<i)) x = t[i][x];

    if(x == y) return x;

    for(i=lg; i>=0; --i)
        if(t[i][x] != t[i][y]) x = t[i][x], y = t[i][y];
    return t[0][x];
}

void solve(int node)
{
    for(auto it : v[node])
        if(it != t[0][node])
        {
            solve(it);
            sum[node] += dp[it];
        }

    dp[node] = sum[node];

    for(auto it : plan[node])
    {
        ll now = aib.query(In[it.x]) + aib.query(In[it.y]) + sum[node] + it.c;
        dp[node] = max(dp[node], now);
    }

    aib.update(In[node], Out[node], sum[node] - dp[node]);
}


int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    int i, x, y, m;

    cin >> n;
    for(i=1; i<n; ++i)
    {
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    dfs(1);

    cin >> m;
    for(i=1; i<=m; ++i)
    {
        int money;
        cin >> x >> y >> money;
        plan[lca(x,y)].push_back({x, y, money});
    }

    solve(1);
    cout << dp[1] << '\n';

    return 0;
}

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