这是一个用树来提升难度的贪心题(蒟蒻理解
首先当你来到一个新节点时有两种情况
1、此节点能被已染色的子节点覆盖 这时只要更新理论最大覆盖范围
2、此节点不能被已染色的子节点覆盖 选择那个提供最大覆盖范围的子节点染***r>菜鸡的其他理解全在代码里面了QAQ
#include <bits/stdc++.h> #define ll long long ll const maxn=1e5+5; using namespace std; struct M{///链式前向星存图 ll to,next,val;///终点,同起点的上一条边的编号,边权 }edge[maxn<<1];///边集 ll n,x,u,v,cnt,head[maxn],k[maxn],ans; void add(ll u,ll v) { edge[++cnt].next = head[u];///以u为起点上一条边的编号,也就是与这个边起点相同的上一条边的编号 edge[cnt].to=v;///终点 //edge[cnt].val=w;///权值 head[u]=cnt;///更新以u为起点上一条边的编号 } int dfs(int u,int fa){ int sum=0; for(int i=head[u];i!=0;i=edge[i].next) if(edge[i].to!=fa)///深搜 sum=max(sum,dfs(edge[i].to,u));///确定染色节点 if(!sum)///该点未被染色范围覆盖 选子节点中的最大范围染色 { ans++; return k[u]-1;///向上移一下减一 } k[fa]=max(k[fa],k[u]-1);///更新子节点能覆盖的最大范围 return sum-1; } int main(){ scanf("%lld",&n); for(int i=2;i<=n;i++) { scanf("%lld",&x); add(x,i); add(i,x); } for(int i=1;i<=n;i++)scanf("%lld",&k[i]); dfs(1,0); cout<<ans<<endl; return 0; }