제출 #899958

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
899958		alexdd	Chase (CEOI17_chase)	C++17	100 / 100	1037 ms	262192 KiB

chase

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,rez;
int p[100005];
int dpup[100005][105];
int dpdown[100005][105][2];
vector<int> con[100005];
void dfs(int nod, int par)
{
    int sump=0;
    for(auto adj:con[nod])
    {
        if(adj!=par)
        {
            dfs(adj,nod);
            sump += p[adj];
        }
    }
    for(int i=1;i<=k;i++)
    {
        dpup[nod][i]=0;
        dpdown[nod][i][0]=0;
        dpdown[nod][i][1]=0;
    }
    dpup[nod][1] = sump + p[par];
    for(auto adj:con[nod])
    {
        if(adj!=par)
        {
            for(int i=1;i<=k;i++)
            {
                rez = max(rez, dpup[adj][i] + dpdown[nod][k-i][0]);
                rez = max(rez, dpup[adj][i] + dpdown[nod][k-i][1] - p[adj]);
            }
            for(int i=1;i<=k;i++)
            {
                dpup[nod][i] = max(dpup[nod][i], dpup[adj][i]);
                dpup[nod][i] = max(dpup[nod][i], dpup[adj][i-1] + sump + p[par] - p[adj]);

                dpdown[nod][i][0] = max(dpdown[nod][i][0], dpdown[adj][i][0]);
                dpdown[nod][i][0] = max(dpdown[nod][i][0], dpdown[adj][i][1] - p[nod]);
                dpdown[nod][i][1] = max(dpdown[nod][i][1], dpdown[adj][i-1][0] + sump + p[par]);
                dpdown[nod][i][1] = max(dpdown[nod][i][1], dpdown[adj][i-1][1] - p[nod] + sump + p[par]);

                dpdown[nod][i][0] = max(dpdown[nod][i][0], dpdown[nod][i-1][0]);
                dpdown[nod][i][1] = max(dpdown[nod][i][1], dpdown[nod][i-1][1]);
            }
        }
    }
    for(int i=1;i<=k;i++)
    {
        dpup[nod][i] = max(dpup[nod][i], dpup[nod][i-1]);
        rez = max(rez, dpup[nod][i]);

        dpdown[nod][i][0] = max(dpdown[nod][i][0], dpdown[nod][i-1][0]);
        dpdown[nod][i][1] = max(dpdown[nod][i][1], dpdown[nod][i-1][1]);
        rez = max(rez, dpdown[nod][i][0]);
        rez = max(rez, dpdown[nod][i][1]);
    }
}
signed main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>p[i];
    int a,b;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
        con[a].push_back(b);
        con[b].push_back(a);
    }
    if(n<=1000)
    {
        for(int i=2;i<=n;i++)
            dfs(i,0);
    }
    dfs(1,0);
    cout<<rez;
    return 0;
}

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