这是一个用树来提升难度的贪心题(蒟蒻理解
首先当你来到一个新节点时有两种情况
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;
}
京公网安备 11010502036488号