제출 #1190446

#제출 시각아이디문제언어결과실행 시간메모리
1190446meisgoodPaprike (COI18_paprike)C++20
100 / 100
82 ms18504 KiB
#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 ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...