Description
Description
给定一棵有 \(n\) 个节点的树。每个节点有一个点权和一个参数。节点 \(i\) 的权值为 \(w_i\)，参数为 \(c_i\)。\(1\) 是这棵树的根。
现在，对每个节点 \(u\)（\(1 \leq u \leq n\)），请在树上你找到最长的一条链 \(v_1, v_2, \dots v_m\)，满足如下条件：
- \(v_1 = u\)。
- 对 \(2 \leq i \leq m\)， 有 \(v_i\) 是 \(v_{i - 1}\) 的父节点。
- 链上节点的点权和不超过 \(c_u\)，即 \(\sum_{j = 1}^m w_{v_j} \leq c_u\)。
对全部的测试点，保证 \(1 \leq u, v \leq n \leq 10^5\)，\(1 \leq p_i \lt i\)，\(1 \leq w_i \leq c_i \leq 10^9\)。
Analysis
一种暴力的方法是对于每个点向上 dfs，直接模拟即可。
实际上我们只需要一遍 dfs 即可解决问题。
注意到“链” 的定义：节点 \(u\) 向上走的路径叫做链。因此我们可以用一个栈动态维护链内元素。每次搜到时入栈，回溯时弹栈。
入栈的不一定是节点本身，也可以是节点的某种信息。本题中我们将每个节点的 \(w\) 到根节点的前缀和入栈。题目要求满足 \(\sum_{j = 1}^m w_{v_j} \leq c_u\) 的最大长度链，即最小化链头下标。容易发现可以二分解决。
令链头为 \(v\)，链尾为 \(u\)，即求 \(\min(v)\) 满足 \(a_u-a_v\le c_u\)。这个式子不好二分，我们移项得 \(a_v\ge a_u-c_u\)。对于 \(\forall u\)，\(a_u-c_u\) 是定值。直接二分即可。
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000100;
int n;
vector <int> Edge[N],stk;
int w[N],c[N];
int ans[N];
void dfs(int u)
{
// cout<<u<<endl;
stk.push_back(stk.back()+w[u]);
int sum = 0 ;
int l = 0 , r = stk.size() - 1;
while(l <= r)
{
// cout<<l<< " "<<r<<endl;
int mid = (l+r) >> 1;
// cout<<mid<<endl;
if(stk.back()-stk[mid] <= c[u] )
{
sum = mid;
r = mid - 1;
}
else l = mid + 1;
}
ans[u] = stk.size() - sum - 1;
for(auto v:Edge[u]) dfs(v);
stk.pop_back();
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=2;i<=n;i++)
{
int p;
cin>>p;
Edge[p].push_back(i);
}
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<=n;i++) cin>>c[i];
stk.push_back(0);
dfs(1);
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
cout<<endl;
return 0;
}