P1612 树上的链
网页链接
P1612 树上的链
题目描述
给定一棵有n nn个节点的树。每个节点有一个点权和一个参数。节点i ii的权值为w i w_iwi，参数为c i c_ici。1 11是这棵树的根。
现在，对每个节点u uu（1 ≤ u ≤ n 1 \leq u \leq n1≤u≤n），请在树上你找到最长的一条链v 1 , v 2 , … v m v_1, v_2, \dots v_mv1,v2,…vm，满足如下条件：
- v 1 = u v_1 = uv1=u。
- 对2 ≤ i ≤ m 2 \leq i \leq m2≤i≤m， 有v i v_ivi是v i − 1 v_{i - 1}vi−1的父节点。
- 链上节点的点权和不超过c u c_ucu，即∑ j = 1 m w v j ≤ c u \sum_{j = 1}^m w_{v_j} \leq c_u∑j=1mwvj≤cu。
输入格式
第一行是一个整数，表示树的节点数n nn。
第二行有n − 1 n - 1n−1个整数p 2 , p 3 , … p n p_2, p_3, \dots p_np2,p3,…pn，其中p i p_ipi表示节点i ii的父节点。
第三行有n nn个整数，第i ii个整数表示节点i ii的权值w i w_iwi。
第四行有n nn个整数，第i ii个整数表示节点i ii的参数c i c_ici。
输出格式
输出一行n nn个用空格隔开的整数，第i ii个整数表示节点i ii对应的链的最长长度。
输入输出样例 #1
输入 #1
5 1 1 2 2 1 2 3 4 5 1 3 3 6 8输出 #1
1 2 1 2 3说明/提示
数据规模与约定
对全部的测试点，保证1 ≤ u , v ≤ n ≤ 10 5 1 \leq u, v \leq n \leq 10^51≤u,v≤n≤105，1 ≤ p i < i 1 \leq p_i \lt i1≤pi<i，1 ≤ w i ≤ c i ≤ 10 9 1 \leq w_i \leq c_i \leq 10^91≤wi≤ci≤109。
解题思路
本题是树上祖先链后缀和 + 二分查找的经典题型。对于每个节点u uu，要求出从u uu出发沿父边向上延伸的一条最长链，使得链上节点权值之和不超过c u c_ucu。利用树的前序遍历性质与权值非负带来的前缀和单调性，可以在 DFS 过程中维护根到当前节点的前缀和栈，并通过二分快速定位最远合法祖先，从而O ( n log n ) O(n\log n)O(nlogn)求出所有答案。
1. 问题等价转化
- 链的限制：所求链必须从u uu开始，不断走向父节点，因此它一定是根到u uu的路径上的一段后缀。
- 权值和约束：设根到u uu路径上各节点权值和为sum ( u ) \text{sum}(u)sum(u)，若链起点为v vv（祖先），终点为u uu，则该链权值和为sum ( u ) − sum ( parent ( v ) ) \text{sum}(u)-\text{sum}(\text{parent}(v))sum(u)−sum(parent(v))。需要满足不超过c u c_ucu。
- 单调性：由于w i ≥ 1 w_i \ge 1wi≥1，从根到任意节点的前缀和严格递增。因此sum ( u ) \text{sum}(u)sum(u)已知，要找最远的v vv，相当于找最小的祖先前缀和S SS，使得sum ( u ) − S ≤ c u \text{sum}(u)-S \le c_usum(u)−S≤cu，即S ≥ sum ( u ) − c u S \ge \text{sum}(u)-c_uS≥sum(u)−cu。前缀和递增，可用二分查找左边界。
- 答案长度：若二分找到的最小前缀和位于栈中下标
ret，则链起点为下标ret+1对应的节点，链长度为当前栈内节点数减去ret，即stk.size() - ret - 1。
2. 算法实现：DFS 维护前缀和栈 + 二分
- 建树：根据输入的父节点数组p 2 … p n p_2 \dots p_np2…pn构建邻接表。
- 初始化前缀和栈：
stk初始放入0 00，表示根节点父亲的前缀和为0 00。 - DFS 遍历：
- 进入节点u uu时，将
stk.back() + w[u]压入栈，得到当前根到u uu的前缀和。 - 在
stk上二分查找最小的下标ret，满足stk.back() - stk[ret] <= c[u]。 - 节点u uu的答案
ans[u] = stk.size() - ret - 1。 - 递归访问所有子节点。
- 回溯时弹出栈顶，恢复祖先链状态。
- 进入节点u uu时，将
- 输出答案：按节点编号顺序输出
ans[i]。
3. 复杂度分析
- 时间复杂度：每个节点入栈、出栈一次，并执行一次二分查找，复杂度O ( log n ) O(\log n)O(logn)。总时间复杂度O ( n log n ) O(n \log n)O(nlogn)，n ≤ 10 5 n \le 10^5n≤105完全可行。
- 空间复杂度：邻接表、权值与答案数组均为O ( n ) O(n)O(n)，前缀和栈深度为树高，最坏O ( n ) O(n)O(n)。
总结
核心思想是将树上向上延伸的链转化为根到当前节点前缀和的一段后缀。利用前缀和单调递增，对每个节点二分出满足限制的最远祖先，即可得到最长合法链长度。DFS 中的前缀和栈自然维护了祖先路径，回溯时弹出恢复，保证每个节点查询的都是其自身到根的链信息。
代码简要说明
- 全局数组：
e[maxn]：邻接表，存储每个节点的子节点。w[], c[], p[], ans[]：分别表示权值、参数、父节点、答案。stk：vector<ll>，用于记录当前 DFS 路径上的前缀和。
- DFS 函数
dfs(u)：- 将当前节点权值加到栈顶前缀和上并压栈。
- 二分查找满足
stk.back() - stk[mid] <= c[u]的最小mid，记为ret。 - 计算
ans[u] = stk.size() - ret - 1。 - 遍历子节点递归调用。
- 回溯时
stk.pop_back()恢复状态。
- 主函数：
- 读入n nn，构建树。
- 读入权值数组和参数数组。
- 初始化
stk为{0}，从根节点1 11开始 DFS。 - 顺序输出所有答案。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;constll maxn=100005;array<vector<ll>,maxn>e;array<ll,maxn>w,c,p,ans;vector<ll>stk;voiddfs(ll u){stk.push_back(w[u]+stk.back());ll ret=0;ll l=0,r=(ll)stk.size()-1,mid;while(l<=r){mid=(l+r)>>1;if(stk.back()-stk[mid]<=c[u]){ret=mid;r=mid-1;}elsel=mid+1;}ans[u]=(ll)stk.size()-ret-1;for(autov:e[u])dfs(v);stk.pop_back();}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n;cin>>n;for(ll i=2;i<=n;i++){cin>>p[i];e[p[i]].push_back(i);}for(ll i=1;i<=n;i++)cin>>w[i];for(ll i=1;i<=n;i++)cin>>c[i];stk.push_back(0);dfs(1);for(ll i=1;i<=n;i++){cout<<ans[i];if(i==n)cout<<endl;elsecout<<' ';}return0;}
