原题传送门
题目大意\(:\)懒得说了\(,\)自己去看吧\((\)逃
首先这道题我赛时一看就感觉是树上差分\(,\)但是我没学过(悲
所以我选择大卫拖把专家寻找一些性质\(:\)
\(1.\)一个节点如果有多个\(y\)值\(,\)那么只需要保留最大的即可\(。\)
\(2.\)每个节点的\(y\)值是具有往下的传递性的\(,\)具体来说就是\(,\)一个节点的\(y\)值减一然后往下传递\(,\)是完全可行并且可以得出正确答案的\(。\)比如\(,\)假设节点\(u\)给它的儿子节点\(v\)安上保险之后\(,\)便可以把\(u\)的\(y\)值减一\((\)减一也就代表已经给\(v\)用了一次\()\)然后直接丢给\(v,\)然后再让\(v\)继续向下传递\(,\)这是完全等价的\(。\)
然后此题就很显然地可以推出\(O(n)\)做法了。就是直接\(dfs\)一遍,在标记给节点安上保险的同时传递\(y\)值,并且只保留最大值然后继续往下标记、传递。
奉上\(AC\) \(Code:\)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define re register
const int N=300010;
int n,m,p[N],y[N];
int idx,head[N];
int fa[N];
bool f[N],vis[N];
//链式向前星存边
struct edge{
int u,v,nxt;
}e[N];
il void adde(int u,int v){
e[++idx]={u,v,head[u]};
head[u]=idx;
}
il void dfs(int x){
if(y[x]>=0)f[x]=1;//如果y值还有剩余就安上保险
for(re int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
y[v]=max(y[v],y[x]-1);//传递，取max
dfs(v);
}
}
il int read(){
re int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
int main(){
n=read(),m=read();
for(re int i=2;i<=n;i++){
p[i]=read();
adde(p[i],i);
}
memset(y,-1,sizeof y);
for(re int i=1;i<=m;i++){
int x=read(),z=read();
y[x]=max(y[x],z);
}
dfs(1);
//统计答案
int ans=0;
for(re int i=1;i<=n;i++)if(f[i])ans++;
printf("%d",ans);
return 0;
}