#include<bits/stdc++.h> using namespace std; const int maxn=2e5+7; inline int lb(int x){return x&(-x);} int n,q; int lc[maxn],rc[maxn],f[maxn][20]; int dp[maxn],Min[maxn],Max[maxn]; int v[maxn],a[maxn]; int dfn; int ST[maxn],ED[maxn],ID[maxn]; int Ans=0; inline void Init(int u){ if(!u)return; ST[u]=dfn+1; Init(lc[u]);ID[u]=++dfn;Init(rc[u]); ED[u]=dfn; Min[u]=Max[u]=a[ID[u]]=v[u]; dp[u]=1; if(lc[u]){ dp[u]&=dp[lc[u]]; Min[u]=min(Min[lc[u]],Min[u]); Max[u]=max(Max[lc[u]],Max[u]); dp[u]&=(Max[lc[u]]<=v[u]); } if(rc[u]){ dp[u]&=dp[rc[u]]; Min[u]=min(Min[rc[u]],Min[u]); Max[u]=max(Max[rc[u]],Max[u]); dp[u]&=(v[u]<=Min[rc[u]]); } Ans+=dp[u]; } struct BIT{ int t[maxn]; inline void Clr(){memset(t,0,sizeof(t));} inline void Add(int x,int dt){ for(int i=x;i<=n;i+=lb(i))t[i]+=dt; } inline int Qry(int x){ int ans=0; for(int i=x;i;i-=lb(i))ans+=t[i]; return ans; } }T; inline bool LE(int u){ return !(T.Qry(ED[u]-1)-T.Qry(ST[u]-1)); } inline void Maintain(int x,int op){ if(x<n)if(a[x]>a[x+1])T.Add(x,op); if(1<x)if(a[x-1]>a[x])T.Add(x-1,op); } inline int C(int x){ if(!LE(x))return 0; int ret=1; for(int i=19;i>=0;i--){ if(!f[x][i])continue; if(LE(f[x][i]))x=f[x][i],ret+=(1<<i); } return ret; } signed main(){ freopen("bst.in","r",stdin); freopen("bst.out","w",stdout); T.Clr(); cin>>n>>q; for(int i=1;i<=n;i++){ cin>>lc[i]>>rc[i]; f[lc[i]][0]=(lc[i]?i:0),f[rc[i]][0]=(rc[i]?i:0); } for(int i=1;i<=n;i++)cin>>v[i]; Init(1); for(int j=1;j<=19;j++)for(int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1]; for(int i=1;i<n;i++)if(a[i]>a[i+1])T.Add(i,1); while(q--){ int p,x; cin>>p>>x; Ans-=C(p); Maintain(ID[p],-1);a[ID[p]]=x;Maintain(ID[p],1); Ans+=C(p);cout<<Ans<<endl; } }