为啥我在外面二分会wa,在dfs里二分就能ac,这有啥区别??
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define cy cout<<"YES"<<endl
#define cn cout<<"NO"<<endl
#define l(rt) rt<<1
#define r(rt) rt<<1|1
const int N=3e5+6,yyx=4e9+7;
int n,k,pre[N],a[N],c[N],d[N],ans[N],st[N];
vector<int> to[N];
inline void dfs(int now,int fa){
pre[now]=pre[fa]+a[now];
d[now]=d[fa]+1;
st[d[now]+1]=now;
// int l=0,r=d[now]+1;
// while(l+1<r){
// int m=l+r>>1;
// if(pre[now]-pre[st[m]]<=c[now]) r=m;//当前m深度的权值和都满足条件,所以深度可以继续减小,即往上(树根)延伸
// else l=m;
// }
//ans[now]=d[now]+1-r;
for(auto v:to[now]){
if(v==now) continue;
dfs(v,now);
}
}
inline void solve(){
cin>>n;
for(int i=2;i<=n;++i){
int p;cin>>p;
to[p].push_back(i);
}
for(int i=1;i<=n;++i) cin>>a[i];
for(int i=1;i<=n;++i) cin>>c[i];
dfs(1,0);
for(int i=1;i<=n;++i){
int l=0,r=d[i]+1;
while(l+1<r){
int m=l+r>>1;
if(pre[i]-pre[st[m]]<=c[i]) r=m;//当前m深度的权值和都满足条件,所以深度可以继续减小,即往上(树根)延伸
else l=m;
}
cout<<d[i]+1-r<<" ";
} //cout<<ans[i]<<" ";
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int _=1;
//cin>>_;
while(_--)
solve();
return 0;
}