oj.uz

Submission #899938

# Submission time Handle Problem Language Result Execution time Memory
899938 2024-01-07T10:30:46 Z alexdd Chase (CEOI17_chase) C++17
0 / 100
 163 ms 96124 KB 
#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);
    }
    dfs(1,0);
    cout<<rez;
    return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Incorrect 1 ms 4700 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Incorrect 1 ms 4700 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 96124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Incorrect 1 ms 4700 KB Output isn't correct
3 Halted 0 ms 0 KB -