Submission #306610

#	Time	Username	Problem	Language	Result	Execution time	Memory
306610		laoriu	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	354 ms	36088 KiB

election_campaign

#define X first
#define Y second
#define pb push_back
#include<bits/stdc++.h>
using namespace std;

typedef pair < int, int > ii;
typedef pair < ii , int > iii;
using ll = long long;
using ld = long double;

const ll MAX=100003,inf=1e18;
vector < int > pr[MAX];
int par[18][MAX];
int F[18][MAX];
int h[MAX];
int dp[MAX];
int sum[MAX];
void DFS(int v,int trc){
    for(int u:pr[v]) if(u!=trc){
        par[0][u]=v;
        h[u]=h[v]+1;
        DFS(u,v);
    }
}
int jump(int v,int d){
    for(int i= 17;i>=0;i--)if(d&(1<<i))
        v=par[i][v];
    return v;
}
int cnt(int i,int v){
    if(F[i][v]!=-1) return F[i][v];
    else return F[i][v]=cnt(i-1,v)+cnt(i-1,par[i-1][v]);
}
int getup(int v,int d){
    int ans=0;
    for(int i=17;i>=0;i--)if(d&(1<<i)){
        ans+=cnt(i,v);
        v=par[i][v];
    }
    return ans;
}
int lca(int u,int v){
    v=jump(v,h[v]-h[u]);
    if(u==v) return u;
    for(int i=17;i>=0;i--)if(par[i][u]!=par[i][v]) {
        u=par[i][u];v=par[i][v];
    }
    return par[0][u];
}
struct path{
    int x,y,c;
    path(){}
    path(int u1,int u2,int u3){
        x=u1;y=u2;c=u3;
    }
};
vector < path > ad[MAX];
void GO(int v,int trc){
    for(int u:pr[v]) if (u!=trc){
        GO(u,v);
        sum[v]+=dp[u];
    }
    for(int u:pr[v]) if (u!=trc){
        F[0][u]=sum[v]-dp[u];
    }
    dp[v]=sum[v];
    for(path e:ad[v]){
        if(e.x!=v){
            dp[v]=max(dp[v],e.c+getup(e.x,h[e.x]-h[v])+getup(e.y,h[e.y]-h[v])+sum[e.x]+sum[e.y]-sum[v]);
        }

        else dp[v]=max(dp[v],e.c+getup(e.y,h[e.y]-h[v])+sum[e.y]);
    }

}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("election.inp","r",stdin);freopen("election.out","w",stdout);
    int n,Q,x,y,c;
    cin>>n;
    memset(F,-1,sizeof F);
    for(int i=1;i<n;i++){
        cin>>x>>y;
        pr[x].pb(y);
        pr[y].pb(x);
    }
    DFS(1,0);
    for(int i=1;i<=17;i++)
        for(int u=1;u<=n;u++)
            par[i][u]=par[i-1][par[i-1][u]];
    cin>>Q;
    while(Q--){
        cin>>x>>y>>c;
        if(h[x]>h[y]) swap(x,y);
        //cout<<x<<' '<<y<<' '<<lca(x,y)<<'\n';
        ad[lca(x,y)].pb(path(x,y,c));
    }
    GO(1,0);
    cout<<dp[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