#include<bits/stdc++.h> using namespace std; #define int long long #define lson (pos<<1) #define rson (pos<<1|1) int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=200010,N=20,inf=1000000000; int n,m,as[MAXN],ans,a[MAXN],l[MAXN],r[MAXN]; int dfn[MAXN],L[MAXN],R[MAXN],dy[MAXN],cnt,f[MAXN][N+5]; int DFN[MAXN],CNT,DY[MAXN],top[MAXN],ty,dep[MAXN],son[MAXN],siz[MAXN]; struct treearray{ int C[MAXN]; int lb(int x){return x&(-x);} void upd(int x,int y){ // cout<<"U"<<x<<" "<<y<<endl; for(int i=x;i<=n;i+=lb(i))C[i]+=y;} int qry(int x){int res=0;for(int i=x;i>=1;i-=lb(i))res+=C[i];return res;} int qry(int l,int r){ // cout<<l<<" "<<r<<":"<<qry(r)-qry(l-1)<<endl; return l>r?0:qry(r)-qry(l-1);} }T; struct segtree{ int t[MAXN<<2],lz[MAXN<<2]; void pushup(int pos){ t[pos]=t[lson]+t[rson]; } void pushdown(int pos,int l,int r){ if(lz[pos]!=-1){ int mid=(l+r)>>1; t[lson]=lz[pos]*(mid-l+1); t[rson]=lz[pos]*(r-mid); lz[lson]=lz[rson]=lz[pos]; lz[pos]=-1; } } void build(int pos,int l,int r){ if(l==r){ t[pos]=as[DY[l]]; return; } pushdown(pos,l,r); int mid=(l+r)>>1; build(lson,l,mid);build(rson,mid+1,r); pushup(pos); } void update(int pos,int l,int r,int ql,int qr,int x){ if(ql<=l&&qr>=r){ t[pos]=(r-l+1)*x; lz[pos]=x; return; } pushdown(pos,l,r); int mid=(l+r)>>1; if(ql<=mid)update(lson,l,mid,ql,qr,x); if(qr>mid)update(rson,mid+1,r,ql,qr,x); pushup(pos); } int query(int pos,int l,int r,int ql,int qr){ if(ql<=l&&qr>=r)return t[pos]; int mid=(l+r)>>1,res=0; pushdown(pos,l,r); if(ql<=mid)res=query(lson,l,mid,ql,qr); if(qr>mid)res+=query(rson,mid+1,r,ql,qr); return res; } void prt(int pos,int l,int r){ if(l==r){ cout<<t[pos]<<" "; return; } int mid=(l+r)>>1; prt(lson,l,mid);prt(rson,mid+1,r); } }TR; void dfs1(int u){ L[u]=cnt+1; if(l[u])dfs1(l[u]); dfn[u]=++cnt,dy[cnt]=u; if(r[u])dfs1(r[u]); R[u]=cnt; } void dfs(int u){ siz[u]=1; if(l[u])dep[l[u]]=dep[u]+1,dfs(l[u]),siz[u]+=siz[l[u]]; if(r[u])dep[r[u]]=dep[u]+1,dfs(r[u]),siz[u]+=siz[r[u]]; if(siz[l[u]]>siz[r[u]])son[u]=l[u]; else son[u]=r[u]; } void dfs2(int u){ DFN[u]=++CNT,DY[CNT]=u,top[u]=ty; if(son[u])dfs2(son[u]); if(son[u]^l[u]^r[u]){ ty=son[u]^l[u]^r[u]; dfs2(son[u]^l[u]^r[u]); } } void upd(int x,int y,int k){ // cout<<x<<" "<<y<<" "<<":"<<k<<endl; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); TR.update(1,1,n,DFN[top[x]],DFN[x],k); x=f[top[x]][0]; } if(DFN[x]>DFN[y])swap(x,y); TR.update(1,1,n,DFN[x],DFN[y],k); } void slv(){ n=read(),m=read(); for(int i=1;i<=n;i++)l[i]=read(),r[i]=read(),f[l[i]][0]=f[r[i]][0]=i;f[1][0]=1; for(int i=1;i<=n;i++)a[i]=read(); dfs1(1); dfs(1); ty=1; dfs2(1); for(int i=1;i<=N;i++)for(int j=1;j<=n;j++)f[j][i]=f[f[j][i-1]][i-1]; for(int i=1;i<=n;i++)if(a[dy[i]]>a[dy[i+1]])T.upd(i,1); // for(int i=1;i<=n;i++)cout<<a[dy[i]]<<" ";cout<<endl; for(int i=1;i<=n;i++)as[i]=!T.qry(L[i],R[i]-1); TR.build(1,1,n); while(m--){ int x=read(),k=read(); // cout<<a[dy[dfn[x]-1]]<<" "<<a[x]<<" "<<a[dy[dfn[x]+1]]<<endl; if(a[x]>a[dy[dfn[x]+1]])T.upd(dfn[x],-1); if(dfn[x]>1&&a[x]<a[dy[dfn[x]-1]])T.upd(dfn[x]-1,-1); a[x]=k; if(a[x]>a[dy[dfn[x]+1]])T.upd(dfn[x],1); if(dfn[x]>1&&a[x]<a[dy[dfn[x]-1]])T.upd(dfn[x]-1,1); int u=x; for(int i=N;~i;i--){ if(!T.qry(L[f[u][i]],R[f[u][i]]-1))u=f[u][i]; } // cout<<u<<" "<<T.qry(L[x],R[x]-1)<<endl; if(!T.qry(L[x],R[x]-1))upd(x,u,1),u=f[u][0]; if(T.qry(L[1],R[1]-1))upd(1,u,0); printf("%lld\n",TR.query(1,1,n,1,n)); // TR.prt(1,1,n);cout<<endl; } } signed main(){ slv(); return 0; }