제출 #578533

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
578533		andrei_boaca	Chase (CEOI17_chase)	C++14	40 / 100	262 ms	524288 KiB

chase

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n,v,p[100005],par[100005],dp[100005][105];
vector<ll> muchii[100005];
ll ans=0,s[100005];
ll MAXROOT=1;
bool use[100005];
multiset<ll> vals[100005][105];
void dfs(int nod)
{
    for(int i=1;i<=v;i++)
        dp[nod][i]=0;
    ll suma=0;
    int cnt=0;
    for(int i:muchii[nod])
        if(i!=par[nod])
        {
            suma+=p[i];
            par[i]=nod;
            cnt++;
            dfs(i);
            for(int j=1;j<=v;j++)
                vals[nod][j].insert(dp[i][j]);
        }
    s[nod]=suma;
    for(int j=1;j<=v;j++)
    {
        dp[nod][j]=dp[nod][j-1];
        for(int i:muchii[nod])
            if(i!=par[nod])
            {
                dp[nod][j]=max(dp[nod][j],dp[i][j]);
                dp[nod][j]=max(dp[nod][j],dp[i][j-1]+s[nod]);
            }
    }
}
void calcdp(int nod,int j)
{
    dp[nod][j]=0;
    if(vals[nod][j].empty())
        return;
    ll x=*prev(vals[nod][j].end());
    ll y=s[nod];
    if(j>1)
        y=*prev(vals[nod][j-1].end())+s[nod];
    dp[nod][j]=max(x,y);
}
void reroot(int nod,int fiu)
{
    s[nod]-=p[fiu];
    s[fiu]+=p[nod];
    par[nod]=fiu;
    par[fiu]=0;
    for(int j=1;j<=v;j++)
        vals[nod][j].erase(vals[nod][j].find(dp[fiu][j]));
    for(int j=1;j<=v;j++)
        calcdp(nod,j);
    for(int j=1;j<=v;j++)
        vals[fiu][j].insert(dp[nod][j]);
    for(int j=1;j<=v;j++)
        calcdp(fiu,j);
}
void calc(int nod)
{
    use[nod]=1;
    ans=max(ans,dp[nod][v]);
    for(int i:muchii[nod])
        if(i!=par[nod]&&!use[i])
        {
            reroot(nod,i);
            calc(i);
            reroot(i,nod);
        }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>v;
    for(int i=1;i<=n;i++)
        cin>>p[i];
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        muchii[a].push_back(b);
        muchii[b].push_back(a);
    }
    dfs(1);
    calc(1);
    cout<<ans;
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30