#include<bits/stdc++.h>
using namespace std;
#define pb push_back
int n,m,a[100005],u_i,v_i,sum[100005],cnt,total,ss,ans=0,w;
vector<int> v[100005];
priority_queue<int> pq;
void dfs(int u,int p)
{
for(auto node:v[u])
{
if(node!=p)dfs(node,u);
}
if(v[u].size()==1&&u!=1)
{
sum[u]=a[u];
//cout << "u=" << u << "||" << "sumu=" << sum[u] << '\n';
}else
{
if(u==1)
{
total=v[1].size();
}else
{
total=v[u].size()-1;
}
cnt=a[u];
//if(u==6)cout << u << '\n';
for(auto node:v[u])
{
if(node!=p)
{
pq.push(-sum[node]);
//if(u==6)cout << node << ' ' << sum[node] << '\n';
}
}
ss=-1;
while(!pq.empty())
{
w=-pq.top();
cnt+=w;
pq.pop();
if(cnt>m)
{
cnt-=w;
ss=pq.size()+1;
break;
}
}
sum[u]=cnt;
if(ss==-1)ss=0;
ans+=ss;
}
}
int main()
{
ios_base::sync_with_stdio(0),cin.tie(0);
cin >> n >> m;
for(int i=1;i<=n;i++)cin >> a[i];
for(int i=1;i<n;i++)
{
cin >> u_i >> v_i;
v[u_i].pb(v_i);
v[v_i].pb(u_i);
}
dfs(1,1);
cout << ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
16384 KB |
Output is correct |
2 |
Correct |
36 ms |
16332 KB |
Output is correct |
3 |
Correct |
48 ms |
16424 KB |
Output is correct |
4 |
Correct |
44 ms |
16384 KB |
Output is correct |
5 |
Correct |
36 ms |
16204 KB |
Output is correct |
6 |
Correct |
37 ms |
16204 KB |
Output is correct |
7 |
Correct |
36 ms |
16204 KB |
Output is correct |
8 |
Correct |
41 ms |
15808 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |