Submission #712328

#	Time	Username	Problem	Language	Result	Execution time	Memory
712328		sofija6	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	287 ms	46156 KiB

election_campaign

#include <bits/stdc++.h>
#define ll long long
#define MAXN 100010
#define logn 19
using namespace std;
vector<ll> G[MAXN],V[MAXN];
ll up[MAXN][logn],in[MAXN],out[MAXN],t=1,D[MAXN],a[MAXN],b[MAXN],c[MAXN],dp[MAXN][2];
void DFS_1(ll i,ll p)
{
    up[i][0]=p;
    in[i]=t;
    D[i]=D[p]+1;
    t++;
    for (ll j=1;j<logn;j++)
        up[i][j]=up[up[i][j-1]][j-1];
    for (ll next : G[i])
    {
        if (next!=p)
            DFS_1(next,i);
    }
    out[i]=t;
    t++;
}
bool Is_Ancestor(ll u,ll v)
{
    return (in[u]<=in[v] && out[u]>=out[v]);
}
ll LCA(ll u,ll v)
{
    if (Is_Ancestor(u,v))
        return u;
    if (Is_Ancestor(v,u))
        return v;
    for (ll i=logn-1;i>=0;i--)
    {
        if (!Is_Ancestor(up[u][i],v))
            u=up[u][i];
    }
    return up[u][0];
}
struct bit
{
    vector<ll> B;
    void Init()
    {
        B.resize(t+2);
    }
    void Add(ll val,ll pos)
    {
        for (ll i=pos;i<t+2;i+=i&(-i))
            B[i]+=val;
    }
    ll Sum(ll pos)
    {
        ll ans=0;
        for (ll i=pos;i>0;i-=i&(-i))
            ans+=B[i];
        return ans;
    }
    ll Calc(ll l,ll r)
    {
        return Sum(r)-Sum(l-1);
    }
};
bit B0,B1;
void DFS_2(ll i,ll p)
{
    for (ll next : G[i])
    {
        if (next!=p)
        {
            DFS_2(next,i);
            dp[i][0]+=max(dp[next][0],dp[next][1]);
        }
    }
    B0.Add(dp[i][0],in[i]);
    B0.Add(-dp[i][0],out[i]);
    for (auto j : V[i])
    {
        dp[i][1]=max(dp[i][1],c[j]+B0.Calc(in[i],in[a[j]])+B0.Calc(in[i],in[b[j]])-dp[i][0]-B1.Calc(in[i]+1,in[a[j]])-B1.Calc(in[i]+1,in[b[j]]));
    }
    B1.Add(max(dp[i][0],dp[i][1]),in[i]);
    B1.Add(-max(dp[i][0],dp[i][1]),out[i]);
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,m,x,y;
    cin >> n;
    for (ll i=1;i<n;i++)
    {
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    DFS_1(1,1);
    cin >> m;
    for (ll i=1;i<=m;i++)
    {
        cin >> a[i] >> b[i] >> c[i];
        V[LCA(a[i],b[i])].push_back(i);
    }
    B0.Init();
    B1.Init();
    DFS_2(1,1);
    cout << max(dp[1][1],dp[1][0]);
    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