Submission #1190446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190446		meisgood	Paprike (COI18_paprike)	C++20	100 / 100	82 ms	18504 KiB

paprike

#include <bits/stdc++.h>
using namespace std ;
#define int long long
bool v[100003] ;
vector <int> adj[100003] ;
int n,k ;
int arr[100003] ;
int tt=0 ;
int sz[100003] ;
void dfs(int x){
    v[x]=1 ;
    vector <int> vv ;
    int ttt=arr[x] ;
    for (auto a : adj[x]){
        if (v[a]) continue ;
        dfs(a) ;
        vv.push_back(sz[a]) ;
        ttt+=sz[a] ;
    }
    sort(vv.begin(),vv.end()) ;
    int i=vv.size()-1 ;
    while (ttt>k){
        ttt-=vv[i] ;
        tt++ ;
        i-- ;
    }
    sz[x]=ttt ;
}
signed main(){
    int i,j ;
    cin >> n >> k ;
    for (i = 1 ; i <= n ; i ++) cin >> arr[i] ;
    for (i = 0 ; i < n-1 ; i ++){
        int a,b ;
        cin >> a >> b ;
        adj[a].push_back(b) ;
        adj[b].push_back(a) ;
    }
    dfs(1) ;
    cout << tt << endl ;
    return 0 ;
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 27 / 27
• Subtask 4: 49 / 49