#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=2e5+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,q,ls[maxn],rs[maxn],a[maxn]; int dfn[maxn],top[maxn],siz[maxn],son[maxn],fa[maxn],ct,df[maxn],dep[maxn],cc; int rnk[maxn]; vector<int>v[maxn]; struct nd {int mn,ct;}; nd operator+(nd a,nd b){ if(a.mn<b.mn)return a; if(b.mn<a.mn)return b; return (nd){a.mn,a.ct+b.ct}; } struct SegTree { struct node { nd x;int lz; }d[maxn<<2]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) #define x(p) d[p].x #define lz(p) d[p].lz void pu(int p){x(p)=x(ls(p))+x(rs(p));} void cl(int p,int v){lz(p)+=v,x(p).mn+=v;} void pd(int p){cl(ls(p),lz(p)),cl(rs(p),lz(p));lz(p)=0;} void bd(int l,int r,int p){lz(p)=0; if(l==r){ x(p)=(nd){0,1};return; }int mid=l+r>>1; bd(l,mid,ls(p)),bd(mid+1,r,rs(p));pu(p); } void modify(int l,int r,int s,int t,int p,int v){ if(l<=s&&t<=r){cl(p,v);return;}pd(p); int mid=s+t>>1; if(l<=mid)modify(l,r,s,mid,ls(p),v);if(r>=mid+1)modify(l,r,mid+1,t,rs(p),v);pu(p); } }T; void dfs(int u){ dep[u]=dep[fa[u]]+1; siz[u]=1; if(ls[u])fa[ls[u]]=u,dfs(ls[u]),siz[u]+=siz[ls[u]]; df[u]=++cc;rnk[cc]=u; if(rs[u])fa[rs[u]]=u,dfs(rs[u]),siz[u]+=siz[rs[u]]; if(siz[ls[u]]>siz[rs[u]])son[u]=ls[u];else son[u]=rs[u]; } void dfs2(int u,int tp){ dfn[u]=++ct,top[u]=tp; if(!son[u]) return; dfs2(son[u],tp); int p=ls[u]^rs[u]^son[u]; if(p)dfs2(p,p); } void Mod(int u,int x){ //cout<<"Mod "<<u<<" "<<x<<endl; while(u){ T.modify(dfn[top[u]],dfn[u],1,n,1,x); u=fa[top[u]]; } } void upd(int u,int sgn,int tg=0){ int u1=rnk[df[u]-1],u2=rnk[df[u]+1]; //if(u==6)cout<<"!6 "<<u1<<" "<<u2<<endl; if(u1&&a[u1]>a[u]){ int p=(dep[u]<dep[u1])?u:u1; Mod(p,sgn); }if(tg)return; if(u2&&a[u]>a[u2]){ int p=(dep[u]<dep[u2])?u:u2; Mod(p,sgn); } } void slv(){ n=read(),q=read(); up(i,1,n)ls[i]=read(),rs[i]=read(); dfs(1);dfs2(1,1); T.bd(1,n,1); up(i,1,n)a[i]=read(); up(i,1,n)upd(i,1,1); //cout<<"! "<<df[6]<<" "<<rnk[df[6]-1]<<" "<<cc<<endl; while(q--){ int x=read(),v=read(); upd(x,-1);a[x]=v;upd(x,1); //cout<<"! "<<T.x(1).mn<<" "<<T.x(1).ct<<endl; printf("%d\n",(T.x(1).mn?0:T.x(1).ct)); } } int main(){ //freopen("bst.in","r",stdin); //freopen("bst.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }