/*
*/
#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;
struct node{
int val,lazy,pos;
};
pii dp2[maxn];
int d[maxn],n,ind[maxn],m,lazy[maxn],h[maxn];
vector<pii>stek[maxn];
vector<node>dp1[maxn];
vector<int>vect[maxn];
void ins(int x,int val,int id){
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;
}
}
void ers(int x,int id){
///printf("USO\n");
while(stek[x].size() && stek[x].back().ss<=id){
lazy[x]-=stek[x].back().ff+lazy[x];
stek[x].pop_back();
}
///printf("IZASO\n");
return;
}
int get_dp(int x,int id){
if(id<dp1[x].back().pos)return 1e9;
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];
l=0;
r=dp1[x].size()-1;
ret=-1;
while(l<=r){
sr=(l+r)/2;
if(dp1[x][sr].pos<=id){
ret=sr;
r=sr-1;
}
else l=sr+1;
}
return min(dp1[x][ret].val+val,dp2[x].ff);
}
void ispis(int x){
for(int i=dp1[x].size()-1;i>=0;i--)printf("%d %d %d | ",dp1[x][i].val,dp1[x][i].lazy,dp1[x][i].pos);
printf("\n");
}
void go(int x,int prv,int val){
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()==0){
swap(ind[x],ind[id]);
continue;
}
if(dp1[ind[x]][0].pos<dp1[ind[id]][0].pos)swap(ind[x],ind[id]);
/// 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]].back().pos+(val-dp2[ind[x]].ss-2)),dp2[ind[x]].ss});
pom=min(pom,{dp2[ind[id]].ff+get_dp(ind[x],dp1[ind[x]].back().pos+(val-dp2[ind[id]].ss-2)),dp2[ind[id]].ss});
///dp1
///printf("%d %d X ID\n",x,id);
///ispis(ind[x]);
/// ispis(ind[id]);
vector<node>v1,v2;
int ind1=dp1[ind[x]].size()-1;
int ind2=dp1[ind[id]].size()-1;
while(ind1>=0 && ind2>=0){
if(dp1[ind[x]][ind1].pos>dp1[ind[id]][ind2].pos){
v2.pb(dp1[ind[id]].back());
dp1[ind[id]].pop_back();
ind2--;
}
else if(dp1[ind[x]][ind1].pos<dp1[ind[id]][ind2].pos){
v1.pb(dp1[ind[x]].back());
dp1[ind[x]].pop_back();
ind1--;
}
else{
v1.pb(dp1[ind[x]].back());
dp1[ind[x]].pop_back();
ind1--;
v2.pb(dp1[ind[id]].back());
dp1[ind[id]].pop_back();
ind2--;
}
}
///printf("%d %d X ID\n",x,id);
ind1=0;
ind2=0;
int minn1=1e9;
int minn2=1e9;
int cnt1=0;
int cnt2=0;
vector<node>fin;
///printf("POCETAK\n");
///for(int i=0;i<v1.size();i++)printf("%d %d %d 111\n",v1[i].val,v1[i].lazy,v1[i].pos);
///for(int i=0;i<v2.size();i++)printf("%d %d %d 22\n",v2[i].val,v2[i].lazy,v2[i].pos);
while(ind1<v1.size() || ind2<v2.size()){
if(ind1>=v1.size()){
cnt2+=v2[ind2].lazy;
v2[ind2].lazy=0;
v2[ind2].val+=cnt2;
minn2=min(minn2,v2[ind2].val);
fin.pb({minn1+minn2,0,v2[ind2].pos});
ind2++;
}
else if(ind2>=v2.size()){
cnt1+=v1[ind1].lazy;
v1[ind1].lazy=0;
v1[ind1].val+=cnt1;
minn1=min(minn1,v1[ind1].val);
fin.pb({minn1+minn2,0,v1[ind1].pos});
ind1++;
}
else if(v1[ind1].pos==v2[ind2].pos){
cnt1+=v1[ind1].lazy;
v1[ind1].lazy=0;
v1[ind1].val+=cnt1;
cnt2+=v2[ind2].lazy;
v2[ind2].lazy=0;
v2[ind2].val+=cnt2;
minn1=min(minn1,v1[ind1].val);
minn2=min(minn2,v2[ind2].val);
fin.pb({minn1+minn2,0,v1[ind1].pos});
ind2++;
ind1++;
}
else if(v1[ind1].pos>v2[ind2].pos){/// prvo v2
cnt2+=v2[ind2].lazy;
v2[ind2].lazy=0;
v2[ind2].val+=cnt2;
minn2=min(minn2,v2[ind2].val);
fin.pb({minn1+minn2,0,v2[ind2].pos});
ind2++;
}
else{
cnt1+=v1[ind1].lazy;
v1[ind1].lazy=0;
v1[ind1].val+=cnt1;
minn1=min(minn1,v1[ind1].val);
fin.pb({minn1+minn2,0,v1[ind1].pos});
ind1++;
}
}
///for(int i=0;i<fin.size();i++)printf("%d %d %d | ",fin[i].val,fin[i].lazy,fin[i].pos);
/// printf(" FIN\n");
///printf("%d %d %d X ID3\n",x,id,fin.size());
ers(x,fin.back().pos);
///printf("%d %d X ID4\n",x,id);
ins(x,cnt1+minn2,fin.back().pos);
///printf("%d %d X ID4\n",x,id);
fin[fin.size()-1].val-=cnt1+minn2;
fin[fin.size()-1].lazy+=cnt1+minn2;
///printf("%d %d X ID4\n",x,id);
while(fin.size()){
dp1[ind[x]].pb(fin.back());
fin.pop_back();
}
///printf("->\n");
///ispis(ind[x]);
///printf("\n\n");
//printf("%d %d X ID\n",x,id);
/// mozda ovaj na 0tom mestu mora posebno da se racuna, da li je on manji od ostalog?
dp2[ind[x]]=pom;
}
///printf("%d %d | %d XX\n",dp2[ind[x]].ff,dp2[ind[x]].ss,x);
///ispis(ind[x]);
if(dp1[ind[x]].size()==0){
if(d[x]){
dp1[ind[x]].pb({0,0,h[x]});
dp2[ind[x]]={1,0};
}
else{
dp1[ind[x]].pb({0,0,h[x]});
dp2[ind[x]]={0,1e8};
}
return;
}
dp2[ind[x]].ss++;
pii pom;
pom={min(dp2[ind[x]].ff,get_dp(ind[x],dp1[ind[x]].back().pos+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;
int cnt1=0;
int last=-2;
while(dp1[ind[x]].size()){
if(cnt1+dp1[ind[x]].back().lazy+dp1[ind[x]].back().val<dp2[ind[x]].ff)break;
///printf("POPOVAO %d %d %d\n",cnt1,dp1[ind[x]].back().lazy,dp1[ind[x]].back().val);
cnt1+=dp1[ind[x]].back().lazy;
last=dp1[ind[x]].back().pos;
dp1[ind[x]].pop_back();
}
ers(ind[x],last);
if(dp1[ind[x]].size()>0){
dp1[ind[x]][dp1[ind[x]].size()-1].lazy+=cnt1;
ins(ind[x],cnt1,dp1[ind[x]].back().pos);
}
dp1[ind[x]].pb({dp2[ind[x]].ff,0,h[x]});
///printf("%d %d %d UBACI\n",dp2[ind[x]].ff-cnt1,cnt1,h[x]);
dp2[ind[x]]=pom;
/*printf("%d %d | %d XX\n",dp2[ind[x]].ff,dp2[ind[x]].ss,x);
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);
int ret=dp2[ind[1]].ff;
if(ret<=m)return true;
else return false;
}
void hp(int x,int prv,int hh){
h[x]=hh;
for(int i=0;i<vect[x].size();i++){
int id=vect[x][i];
if(id==prv)continue;
hp(id,x,hh+1);
}
}
int main(){
///freopen("test.in","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]);
for(int i=1;i<n;i++){
int u,v;
scanf("%d %d",&u,&v);
vect[u].pb(v);
vect[v].pb(u);
}
hp(1,0,1);
int l=0;
int r=n;
int sr,ret=-1;
while(l<=r){
sr=(l+r)/2;
if(check(sr)){
ret=sr;
r=sr-1;
}
else l=sr+1;
}
///printf("%d AA\n",check(5));
printf("%d\n",ret);
return 0;
}
Compilation message
dyn.cpp: In function 'void go(int, int, int)':
dyn.cpp:94:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(int j=0;j<vect[x].size();j++){
| ~^~~~~~~~~~~~~~~
dyn.cpp:159:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
159 | while(ind1<v1.size() || ind2<v2.size()){
| ~~~~^~~~~~~~~~
dyn.cpp:159:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
159 | while(ind1<v1.size() || ind2<v2.size()){
| ~~~~^~~~~~~~~~
dyn.cpp:162:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | if(ind1>=v1.size()){
| ~~~~^~~~~~~~~~~
dyn.cpp:174:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
174 | else if(ind2>=v2.size()){
| ~~~~^~~~~~~~~~~
dyn.cpp: In function 'void hp(int, int, int)':
dyn.cpp:331:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
331 | for(int i=0;i<vect[x].size();i++){
| ~^~~~~~~~~~~~~~~
dyn.cpp: In function 'int main()':
dyn.cpp:343:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
343 | scanf("%d %d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~
dyn.cpp:344:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
344 | for(int i=1;i<=n;i++)scanf("%d",&d[i]);
| ~~~~~^~~~~~~~~~~~
dyn.cpp:347:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
347 | scanf("%d %d",&u,&v);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
23808 KB |
Output is correct |
| 2 |
Correct |
16 ms |
23808 KB |
Output is correct |
| 3 |
Correct |
16 ms |
23808 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 |
18 ms |
23808 KB |
Output is correct |
| 3 |
Correct |
19 ms |
23808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
24064 KB |
Output is correct |
| 2 |
Correct |
18 ms |
23936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
23888 KB |
Output is correct |
| 2 |
Correct |
20 ms |
23936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
24816 KB |
Output is correct |
| 2 |
Incorrect |
103 ms |
25464 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
411 ms |
28792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1072 ms |
33248 KB |
Output is correct |
| 2 |
Correct |
929 ms |
32352 KB |
Output is correct |
| 3 |
Correct |
807 ms |
30600 KB |
Output is correct |
| 4 |
Correct |
1254 ms |
49500 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2489 ms |
42744 KB |
Output is correct |
| 2 |
Correct |
2624 ms |
43572 KB |
Output is correct |
| 3 |
Runtime error |
431 ms |
65540 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3040 ms |
56316 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
440 ms |
65540 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
