P1612 树上的链网页链接P1612 树上的链题目描述给定一棵有n nn个节点的树。每个节点有一个点权和一个参数。节点i ii的权值为w i w_iwi​参数为c i c_ici​。1 11是这棵树的根。现在对每个节点u uu1 ≤ 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∑j1m​wvj​​≤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输入 #15 1 1 2 2 1 2 3 4 5 1 3 3 6 8输出 #11 2 1 2 3说明/提示数据规模与约定对全部的测试点保证1 ≤ u , v ≤ n ≤ 10 5 1 \leq u, v \leq n \leq 10^51≤u,v≤n≤1051 ≤ p i i 1 \leq p_i \lt i1≤pi​i1 ≤ 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则链起点为下标ret1对应的节点链长度为当前栈内节点数减去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。递归访问所有子节点。回溯时弹出栈顶恢复祖先链状态。输出答案按节点编号顺序输出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[]分别表示权值、参数、父节点、答案。stkvectorll用于记录当前 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。顺序输出所有答案。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll maxn100005;arrayvectorll,maxne;arrayll,maxnw,c,p,ans;vectorllstk;voiddfs(ll u){stk.push_back(w[u]stk.back());ll ret0;ll l0,r(ll)stk.size()-1,mid;while(lr){mid(lr)1;if(stk.back()-stk[mid]c[u]){retmid;rmid-1;}elselmid1;}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;cinn;for(ll i2;in;i){cinp[i];e[p[i]].push_back(i);}for(ll i1;in;i)cinw[i];for(ll i1;in;i)cinc[i];stk.push_back(0);dfs(1);for(ll i1;in;i){coutans[i];if(in)coutendl;elsecout ;}return0;}