Submission #578505

#	Time	Username	Problem	Language	Result	Execution time	Memory
578505		andrei_boaca	Chase (CEOI17_chase)	C++14	0 / 100	152 ms	96144 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;
ll MAXROOT=1;
void dfs(int nod)
{
    for(int i=1;i<=v;i++)
        dp[nod][i]=0;
    ll suma=p[nod];
    for(int i:muchii[nod])
        if(i!=par[nod])
        {
            suma+=p[i];
            par[i]=nod;
            dfs(i);
        }
    dp[nod][1]=suma;
    for(int j=2;j<=v;j++)
    {
        dp[nod][j]=dp[nod][j-1];
        for(int i:muchii[nod])
            if(i!=par[nod])
            {
                ll val=dp[i][j-1]+suma-p[i];
                dp[nod][j]=max(dp[nod][j],val);
            }
    }
}
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);
    }
    if(n<=1000)
        MAXROOT=n;
    for(int root=1;root<=MAXROOT;root++)
    {
        for(int i=1;i<=n;i++)
            par[i]=0;
        dfs(root);
        ans=max(ans,dp[root][v]-p[root]);
    }
    cout<<ans;
    return 0;
}

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