제출 #210344

#제출 시각아이디문제언어결과실행 시간메모리
210344joylintpPaprike (COI18_paprike)C++14
24 / 100
68 ms17796 KiB
#include<bits/stdc++.h> using namespace std; //#pragma gcc optimize("O3,unroll-loop") //#pragma gcc target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,abm,mmx,popcnt,tune=native") //#define int long long bool vis[100001]; int n, kk, val[100001], dp[100001], ans; vector<int> edge[100001]; int dfs(int k) { vis[k] = true; vector<int> vs; dp[k] = val[k]; for (int i : edge[k]) if (!vis[i]) { int t = dfs(i); vs.push_back(t), dp[k] += t; } sort(vs.begin(), vs.end(), greater<int>()); int t = 0; while (dp[k] > kk) dp[k] -= vs[t], t++, ans++; return dp[k]; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> kk; for (int i = 1; i <= n; i++) cin >> val[i]; int a, b; for (int i = 1; i < n; i++) cin >> a >> b, edge[a].push_back(b), edge[b].push_back(a); dfs(1); cout << ans << '\n'; 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...