Submission #1026611

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026611		12345678	Chase (CEOI17_chase)	C++17	40 / 100	4034 ms	94724 KiB

chase

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5, kx=105;

#define ll long long

ll n, k, b[nx], u, v, sm[nx], dp[nx][kx], res;
vector<ll> d[nx];

void dfs(int u, int p)
{
    sm[u]=0;
    for (auto v:d[u]) if (v!=p) sm[u]+=b[v];
    for (int i=1; i<=k; i++) dp[u][i]=max(dp[p][i], dp[p][i-1]+sm[u]), res=max(res, dp[u][i]); //cout<<"debug "<<u<<' '<<i<<' '<<dp[u][i]<<'\n';
    for (auto v:d[u]) if (v!=p) dfs(v, u);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k;
    for (int i=1; i<=n; i++) cin>>b[i];
    for (int i=1; i<n; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u);
    for (int rt=1; rt<=n; rt++)
    {
        for (int i=0; i<=k; i++) for (int j=1; j<=n; j++) dp[j][i]=0;
        //cout<<"root "<<rt<<'\n';
        dfs(rt, 0);
    }
    cout<<res;
}

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