| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1122792 | Choco | Paprike (COI18_paprike) | C++17 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define Study ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define ff first
#define ss second
#define ins insert
#define all(x) x.begin(),x.end()
#define fori(x,y,z) for(ll x=y;x<=z;x++)
const ll INF=1e9;
const ll sz=1e5+10;
const ll mod=1e9+7;
vector<vector<ll>>graph;
vector<ll>check,parent,value,a,cr;
ll k;
void dfs(ll s,ll p=-1){
check[s]=1;
parent[s]=p;
value[s]+=a[s];
for(auto i:graph[s]){
if(!check[i]){
dfs(i,s);
value[s]+=value[i];
}
}
}
bool temp(ll x,ll y){
return value[x]>=value[y];
}
ll cuts=0;
void dfs1(ll s){
if(value[s]>k){
for(auto i:graph[s]){
if(i==parent[s])
continue;
if(value[i]>k){
dfs1(i);
cr[s]+=cr[i];
}
if(value[i]<=k and value[s]-cr[s]>k){
//cout<<i<<' '<<s<<endl;
cr[s]+=value[i];
parent[i]=-1;
cuts++;
}
if(value[s]-cr[s]<=k)
break;
}
value[s]-=cr[s];
}
}
void work(){
ll n;
cin>>n>>k;
graph.resize(n+10);
check.assign(n+10,0);
parent.assign(n+10,-1);
value.assign(n+10,0);
a.resize(n+10);
cr.assign(n+10,0);
ll csum=0;
fori(i,1,n)
cin>>a[i];
fori(i,1,n-1){
ll x,y;
cin>>x>>y;
graph[x].pb(y);
graph[y].pb(x);
}
dfs(1);
//fori(i,1,n)
//cout<<value[i]<<' ';
//cout<<endl;
fori(i,1,n){
sort(all(graph[i]),temp);
}
dfs1(1);
cout<<cuts;
}