이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= (a); i--)
#define pb(x) push_back(x)
int n, res;
long long k, s[100015], d[100015];
vector<int> a[100015];
void dfs(int u, int p)
{
int child = 0;
for(int v : a[u])
if(v != p) dfs(v, u), ++child;
if (child<1)
{
d[u] = s[u];
return;
}
long long sum = s[u];
vector<long long> b;
for(int v : a[u])
if(v != p) b.pb(d[v]);
sort(b.begin(), b.end());
FOR(i,0,(int)b.size())
if(sum+b[i]>k) res +=(int)b.size()-i;
else sum += b[i];
d[u] = sum;
}
int main()
{
cin >> n >> k;
FOR(i,1,n+1) cin >> s[i];
FOR(i,0,n-1)
{
int u,v; cin >> u >> v;
a[u].pb(v);
a[v].pb(u);
}
dfs(1, -1);
cout << res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |