/*
*/
#include<bits/stdc++.h>
#include<set>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define ll long long
typedef pair<int,int> pii;
typedef set<int>::iterator sit;
const int maxn=3e5+10;
pii dp2[maxn];
int d[maxn],n,ind[maxn],m,lazy[maxn];
vector<pii>stek[maxn],dp1[maxn];
vector<int>vect[maxn];
void ins(int x,int val,int id){
///printf("%d ALZY\n",lazy);
if(stek[x].size()==0){
stek[x].pb({-lazy[x],id});
lazy[x]+=val;
return;
}
if(stek[x].back().ss==id)lazy[x]+=val;
else{
stek[x].pb({-lazy[x],id});
lazy[x]+=val;
}
/// printf("%d ALZY\n",lazy);
}
void ers(int x,int id){
///printf("%d ALZY22\n",lazy);
while(stek[x].size() && stek[x].back().ss>=id){
lazy[x]-=stek[x].back().ff+lazy[x];
stek[x].pop_back();
}
///printf("%d ALZY22\n",lazy);
return;
}
int get_dp(int x,int id){
if(id>=(int)dp1[x].size())return 1e9;
id=max(id,0);
int l=0;
int r=stek[x].size()-1;
int ret=-1,sr;
while(l<=r){
sr=(l+r)/2;
if(stek[x][sr].ss>=id){
ret=sr;
r=sr-1;
}
else l=sr+1;
}
int val=0;
if(ret!=-1)val=stek[x][ret].ff+lazy[x];
///printf("%d %d %d JOOOJ\n",dp1[x][id].ff,val,lazy[x]);
return dp1[x][id].ff+val;
}
void ispis(int x){
for(int i=dp1[x].size()-1;i>=0;i--)printf("%d %d | ",dp1[x][i].ff,dp1[x][i].ss);
printf("\n");
}
void go(int x,int prv,int val){
///printf("%d %d AAAA\n",x,prv);
ind[x]=x;
for(int j=0;j<vect[x].size();j++){
int id=vect[x][j];
if(id==prv)continue;
go(id,x,val);
if(dp1[ind[x]].size()<dp1[ind[id]].size())swap(ind[x],ind[id]);
///printf("%d IDIDIDID\n",id);
///if(dp1[ind[x]].size()>0)printf("%d %d | %d %d !!! %d %d \n",dp2[ind[x]].ff,dp2[ind[x]].ss,dp1[ind[x]][0].ff,dp1[ind[x]][0].ss,dp1[ind[x]][1].ff,dp1[ind[x]][1].ss);
///if(dp1[ind[id]].size()>0)printf("%d %d | %d %d !!! %d %d \n",dp2[ind[id]].ff,dp2[ind[id]].ss,dp1[ind[id]][0].ff,dp1[ind[id]][0].ss,dp1[ind[id]][1].ff,dp1[ind[id]][1].ss);
if(dp1[ind[id]].size()==0)continue;
/// merge trees
/// dp2
pii pom;
pom={dp2[ind[x]].ff+dp2[ind[id]].ff,min(dp2[ind[x]].ss,dp2[ind[id]].ss)};
pom=min(pom,{dp2[ind[x]].ff+get_dp(ind[id],dp1[ind[id]].size()-(val-dp2[ind[x]].ss-2)-2),dp2[ind[x]].ss});
pom=min(pom,{dp2[ind[id]].ff+get_dp(ind[x],dp1[ind[x]].size()-(val-dp2[ind[id]].ss-2)-2),dp2[ind[id]].ss});
///dp1
int cnt1=0,cnt2=0;
int ind1=dp1[ind[x]].size()-1;
int ind2=dp1[ind[id]].size()-1;
for(int i=dp1[ind[id]].size()-1;i>=max(0,(int)dp1[ind[id]].size()-val-2);i--){
cnt1=dp1[ind[x]][ind1].ss;
cnt2=dp1[ind[id]][ind2].ss;
ers(ind[x],ind1);
ers(ind[id],ind2);
dp1[ind[x]][ind1].ss=0;
dp1[ind[id]][ind2].ss=0;
dp1[ind[x]][ind1].ff+=cnt1;
dp1[ind[id]][ind2].ff+=cnt2;
dp1[ind[x]][ind1].ff+=min(dp1[ind[id]][ind2].ff,dp2[ind[id]].ff);
///printf("%d %d | %d %d || %d\n",dp1[ind[x]][ind1].ff,dp1[ind[id]][ind2].ff,ind1,ind2,x);
ind1--;
ind2--;
ins(ind[x],cnt1,ind1);
if(ind1>0)dp1[ind[x]][ind1].ss+=cnt1;
ins(ind[id],cnt2,ind2);
if(ind2>0)dp1[ind[id]][ind2].ss+=cnt2;
}
ind2++;
if(ind1>0)dp1[ind[x]][ind1].ss+=min(dp1[ind[id]][ind2].ff,dp2[ind[id]].ff);
ins(ind[x],min(dp1[ind[id]][ind2].ff,dp2[ind[id]].ff),ind1);
/// mozda ovaj na 0tom mestu mora posebno da se racuna, da li je on manji od ostalog?
dp1[ind[x]][dp1[ind[x]].size()-1].ff=pom.ff;
dp2[ind[x]]=pom;
}
///printf("%d %d XXXXLAZYYYYY\n",lazy,x);
if(dp1[ind[x]].size()==0){
if(d[x]){
dp1[ind[x]].pb({0,0});
dp1[ind[x]].pb({1,0});
dp2[ind[x]]={1,0};
}
else{
dp1[ind[x]].pb({0,0});
dp1[ind[x]].pb({0,0});
dp2[ind[x]]={0,1e8};
}
/*printf("%d XX\n",x);
printf("%d %d | \n",dp2[ind[x]].ff,dp2[ind[x]].ss);
ispis(ind[x]);*/
return;
}
/*printf("%d XX\n",x);
printf("%d %d | \n",dp2[ind[x]].ff,dp2[ind[x]].ss);
ispis(ind[x]);*/
dp2[ind[x]].ss++;
pii pom;
///printf("%d LAZYYYYY\n",lazy);
///printf("%d %d AAAAA\n",get_dp(ind[x],dp1[ind[x]].size()-val-1),dp1[ind[x]].size()-val-1);
pom={min(dp2[ind[x]].ff,get_dp(ind[x],dp1[ind[x]].size()-val-1))+1,0};
if(d[x]==0 || dp2[ind[x]].ss<=val)pom=min(pom,dp2[ind[x]]);
///if(pom.ff==0)pom.ss=1e8;
ers(ind[x],dp1[ind[x]].size()-1);
ins(ind[x],dp1[ind[x]][dp1[ind[x]].size()-1].ss,dp1[ind[x]].size()-2);
if(dp1[ind[x]].size()>1)dp1[ind[x]][dp1[ind[x]].size()-2].ss=dp1[ind[x]][dp1[ind[x]].size()-1].ss;
dp1[ind[x]][dp1[ind[x]].size()-1].ss=0;
dp1[ind[x]][dp1[ind[x]].size()-1]={min(dp2[ind[x]].ff,pom.ff),0};
dp1[ind[x]].pb({pom.ff,0});
dp2[ind[x]]=pom;
/*printf("%d XX\n",x);
printf("%d %d | \n",dp2[ind[x]].ff,dp2[ind[x]].ss);
ispis(ind[x]);*/
}
bool check(int x){
memset(dp2,0,sizeof(dp2));
for(int i=1;i<=n;i++){
dp1[i].clear();
stek[i].clear();
lazy[i]=0;
}
go(1,0,x);
if(dp2[ind[1]].ff<=m)return true;
else return false;
}
int main(){
///freopen("test2.txt","r",stdin);
///freopen("out.txt","w",stdout);
/// OPTIMISATION WHEN IT CANT SOLVE A SUBTREE THEN BREAK ALL
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&d[i]);
///if(n>10000)return 123;
for(int i=1;i<n;i++){
int u,v;
scanf("%d %d",&u,&v);
vect[u].pb(v);
vect[v].pb(u);
}
int l=0;
int r=n;
int sr,ret=-1;
while(l<=r){
sr=(l+r)/2;
///printf("%d %d %d AAA\n",l,sr,r);
if(check(sr)){
ret=sr;
r=sr-1;
}
else l=sr+1;
}
///printf("%d CEHCK\n",check(5));
///printf("%d CEHCK\n",check(1));
printf("%d\n",ret);
return 0;
}
Compilation message
dyn.cpp: In function 'void go(int, int, int)':
dyn.cpp:80:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int j=0;j<vect[x].size();j++){
| ~^~~~~~~~~~~~~~~
dyn.cpp: In function 'int main()':
dyn.cpp:211:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
211 | scanf("%d %d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~
dyn.cpp:212:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
212 | for(int i=1;i<=n;i++)scanf("%d",&d[i]);
| ~~~~~^~~~~~~~~~~~
dyn.cpp:217:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
217 | scanf("%d %d",&u,&v);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
23808 KB |
Output is correct |
| 2 |
Correct |
16 ms |
23808 KB |
Output is correct |
| 3 |
Correct |
16 ms |
23936 KB |
Output is correct |
| 4 |
Correct |
16 ms |
23808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
23808 KB |
Output is correct |
| 2 |
Correct |
17 ms |
23808 KB |
Output is correct |
| 3 |
Correct |
17 ms |
23808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
23936 KB |
Output is correct |
| 2 |
Correct |
18 ms |
23936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
23936 KB |
Output is correct |
| 2 |
Correct |
20 ms |
23936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
24888 KB |
Output is correct |
| 2 |
Correct |
96 ms |
25452 KB |
Output is correct |
| 3 |
Incorrect |
131 ms |
26752 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
301 ms |
29252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
829 ms |
33400 KB |
Output is correct |
| 2 |
Correct |
796 ms |
32632 KB |
Output is correct |
| 3 |
Correct |
887 ms |
30712 KB |
Output is correct |
| 4 |
Correct |
1050 ms |
43108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1959 ms |
41080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3079 ms |
51048 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
436 ms |
65540 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
