제출 #1043921

#제출 시각아이디문제언어결과실행 시간메모리
1043921vjudge1Paprike (COI18_paprike)C++17
11 / 100
42 ms604 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e3 + 10; int n, k, a[N], sz[N], ans, tmp; vector<int> g[N]; void dfs(int v, int p = -1){ vector<int> vec; sz[v] = a[v]; for (int u : g[v]){ if (u == p) continue; dfs(u, v); sz[v] += sz[u]; vec.push_back(sz[u]); } sort(vec.begin(), vec.end()); while (sz[v] > k){ sz[v] -= vec.back(); vec.pop_back(); tmp++; } } int main(){ cin >> n >> k; for (int i = 1; i <= n; i ++) cin >> a[i]; for (int i = 1; i < n; i ++){ int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } ans = 1e9; for (int v = 1; v <= n; v ++){ tmp = 0; dfs(v); ans = min(ans, tmp); } cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...