```
#include<iostream>
#include<vector>
#include<cmath>
#define M 10005
using namespace std;
vector<int> edge[M];
int fa[M],w[M],v[M],depth[M],dis[M];
int n,u;
void dfs(int u,int fa){
depth[u]=depth[fa]+1;
dis[u]=dis[fa]+v[u];
for(int i=0;i<edge[u].size();i++){
dfs(edge[u][i],u);
}
}
int main(){
cin>>n;
edge[0].push_back(1);
for(int i=2;i<=n;i++){
cin>>u;
edge[u].push_back(i);
fa[i]=u;
}
for(int i=1;i<=n;i++) cin>>v[i];
for(int i=1;i<=n;i++) cin>>w[i];
dfs(1,0);
// for(int i=1;i<=n;i++){
// cout<<depth[i]<<' '<<dis[i]<<endl;
// }
int l,r,ans,mid;
for(int i=1;i<=n;i++){
l=1,r=depth[i];
while(l<r){
mid=(l+r)>>1;
if(dis[mid]>w[i]){
r=mid;
}
if(dis[mid]<=w[i]){
l=mid+1;
ans=max(ans,mid);
}
}
cout<<ans<<' ';
}
return 0;
}
5
1 1 2 2
1 2 3 4 5
1 3 3 6 8
by 菜のcrzOvO @ 2023-07-13 11:23:12
@[crzcqh](/user/769006) 你这个二分有问题,二分的应该是一条链,你的代码里 ```l=1,r=depth[i];``` 显然是错误的。
这里建议你在 dfs 的时候去二分。(还有应该是要开 ```long long``` 的)
哦对了,你数组还没开够。
```cpp
#include<iostream>
#include<vector>
#include<cmath>
#define M 100005
using namespace std;
vector<long long> edge[M];
long long fa[M],w[M],v[M],depth[M],dis[M];
long long n,u,st[M],top,ans[M];
void dfs(long long u,long long fa){
st[++top]=u;
depth[u]=depth[fa]+1;
dis[u]=dis[fa]+v[u];
long long l=0,r=top,mid;
while(l<=r){
mid=l+r>>1;
if(dis[u]-dis[st[mid]]>w[u]) l=mid+1;
else r=mid-1,ans[u]=top-mid;
}
for(long long i=0;i<edge[u].size();i++) dfs(edge[u][i],u);
top--;
}
int main(){
cin>>n;
edge[0].push_back(1);
for(long long i=2;i<=n;i++){
cin>>u;
edge[u].push_back(i);
fa[i]=u;
}
for(long long i=1;i<=n;i++) cin>>v[i];
for(long long i=1;i<=n;i++) cin>>w[i];
dfs(1,0);
for(long long i=1;i<=n;i++) cout<<ans[i]<<" ";
return 0;
}
```
by One_JuRuo @ 2023-07-27 17:26:46