CF682C这道题如果正着思考 很难想明白 如果倒着思考 就是 一个节点u 如果他的祖先中 存在某个祖先使得u到祖先的边权和大于u的点权 那么这个点就要去掉 显然他的子树也要去掉 所以我们要找最长的边权和 判断与节点点权的关系 类似于最大子段和 如果前面的距离已经小于0了 那么就去掉前面的 重新开始也就是max(0,last)edge[i]; 如果某个节点不符合 那么就停止遍历这个节点和他的子树 如果符合 就继续遍历 最后总点数减去遍历过的点数就是答案代码如下#include bits/stdc.h using namespace std; const int N1e55; int a[N]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cinn; vectorinte(n1,0); vectorvectorinttree(n1); for(int i0;in;i)cina[i]; for(int i1;in;i){ int u; cinue[i]; u--; tree[u].push_back(i); } vectorintdp(n1,0),stk{0}; int ans0; while(!stk.empty()){ int ustk.back(); stk.pop_back(); ans; for(auto v:tree[u]){ dp[v]max(0,dp[u])e[v]; if(dp[v]a[v])stk.emplace_back(v); } } coutn-ans\n; return 0; }