为啥会wa,一定要在dfs中二分吗?
查看原帖
为啥会wa,一定要在dfs中二分吗?
1122530
elpsconr楼主2024/8/3 12:52

为啥我在外面二分会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;
}
2024/8/3 12:52
加载中...