제출 #794223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
794223		mrwang	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	179 ms	48180 KiB

election_campaign

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll P[maxN][18];
ll h[maxN],in[maxN],out[maxN];
ll lca(ll u,ll v)
{
    if(h[u]<h[v]) swap(u,v);
    for(int i=17;i>=0;i--) if(h[u]-(1<<i)>=h[v]) u=P[u][i];
    if(u==v) return u;
    for(int i=17;i>=0;i--) if(P[u][i]!=P[v][i]) u=P[u][i],v=P[v][i];
    return P[u][0];
}
vector<ll>g[maxN];
ll tg=0;
void dfs(ll u,ll p)
{
    P[u][0]=p;in[u]=++tg;
    for(int i=1;i<=17;i++) P[u][i]=P[P[u][i-1]][i-1];
    for(int v:g[u])
    {
        if(v!=p)
        {
            h[v]=h[u]+1;
            dfs(v,u);
        }
    }
    out[u]=tg;
}
ll dp[maxN];
struct qq
{
    ll x,y,w;
};
vector<qq>vec[maxN];
ll bit[maxN];
ll n;
void update(ll i,ll v)
{
    while(i<=n)
    {
        bit[i]+=v;
        i+=i&(-i);
    }
}
ll get(ll i)
{
    ll ans=0;
    while(i>0)
    {
        ans+=bit[i];
        i-=i&(-i);
    }
    return ans;
}
void DFS(ll u,ll p)
{
    for(int v:g[u])
    {
        if(v!=p)
        {
            DFS(v,u);
            dp[u]+=dp[v];
        }
    }
    ll x=dp[u];
    for(auto zz:vec[u])
    {
        dp[u]=max(dp[u],get(in[zz.x])+get(in[zz.y])+x+zz.w);
        if(u==5&&zz.x==6&&zz.y==2)
        {
            cout << get(in[zz.x])<< ' '<<get(in[zz.y])<<' '<<x<<' '<<zz.x<<'\n';
        }
    }
    update(in[u],x-dp[u]);
    update(out[u]+1,dp[u]-x);
}
ll m,k;
void solve()
{
    cin >>n;
    for(int i=1;i<n;i++)
    {
        ll u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1,1);
    //for(int i=1;i<=n;i++) cout << in[i]<<' ';
    //cout << '\n';
    cin >> m;
    for(int i=1;i<=m;i++)
    {
        ll x,y,w;
        cin >> x>> y>> w;
        k=lca(x,y);
        vec[k].pb({x,y,w});
        //cout << k<<' '<<x<<' '<<y<<'\n';
    }
    DFS(1,1);
    cout << dp[1];
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    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