제출 #578558

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

chase

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int need=2;
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];
ll max1[100005][105],max2[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++)
            {
                if(dp[i][j]>max1[nod][j])
                {
                    max2[nod][j]=max1[nod][j];
                    max1[nod][j]=dp[i][j];
                }
                else
                    if(dp[i][j]>max2[nod][j])
                        max2[nod][j]=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;
    ll x=max1[nod][j];
    ll y=s[nod];
    y=max1[nod][j-1]+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++)
    {
        if(dp[fiu][j]==max1[nod][j])
        {
            max1[nod][j]=max2[nod][j];
            max2[nod][j]=0;
        }
        else
            if(dp[fiu][j]==max2[nod][j])
                max2[nod][j]=0;
    }
    for(int j=1;j<=v;j++)
        calcdp(nod,j);
    for(int j=1;j<=v;j++)
    {
        if(dp[nod][j]>max1[fiu][j])
        {
            max2[fiu][j]=max1[fiu][j];
            max1[fiu][j]=dp[nod][j];
        }
        else
            if(dp[nod][j]>max2[fiu][j])
                max2[fiu][j]=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: 30 / 30
• Subtask 4: 30 / 30