제출 #899942

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

chase

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,rez;
int p[100005];
int dp[100005][105];
int aux[105];
int aux2[105];
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=0;i<=k;i++)
        dp[nod][i]=aux[i]=aux2[i]=0;
    dp[nod][1] = sump + p[par];
    for(auto adj:con[nod])
    {
        if(adj!=par)
        {
            for(int i=1;i<=k;i++)
            {
                dp[nod][i] = max(dp[nod][i], dp[adj][i]);
                dp[nod][i] = max(dp[nod][i], dp[adj][i-1] + sump + p[par] - p[adj]);
            }
        }
    }
    for(int i=1;i<=k;i++)
    {
        dp[nod][i] = max(dp[nod][i], dp[nod][i-1]);
        rez = max(rez, dp[nod][i]);
        //cout<<nod<<" "<<i<<"   "<<dp[nod][i]<<"\n";
    }
}
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=1;i<=n;i++)
            dfs(i,0);
    }
    else
        dfs(1,0);
    cout<<rez;
    return 0;
}

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