#pragma GCC optimize("Ofast,no-stack-protector") #include <bits/stdc++.h> using namespace std; int l[200005], r[200005], fa[200005], mi[200005], mx[200005], v[200005], ans; bool b[200005]; inline int read() { int x = 0; bool fl = 0; char c = getchar_unlocked(); while (c < '0' || c > '9') { if (c == '-') fl = 1; c = getchar_unlocked(); } while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar_unlocked(); } return fl ? -x : x; } inline void dfs(int u) { if (l[u] != 0) { dfs(l[u]); } if (r[u] != 0) dfs(r[u]); mi[u] = v[u]; mx[u] = v[u]; b[u] = 1; if (l[u] != 0) { b[u] = b[u] && b[l[u]] && mx[l[u]] <= v[u]; mi[u] = min(mi[u], mi[l[u]]); mx[u] = max(mx[u], mx[l[u]]); } if (r[u] != 0) { b[u] = b[u] && b[r[u]] && mi[r[u]] >= v[u]; mi[u] = min(mi[u], mi[r[u]]); mx[u] = max(mx[u], mx[r[u]]); } // if (b[u]) // printf("s%lld\n", u); ans += b[u]; } inline void upd(int u, int x) { v[u] = x; mi[u] = v[u]; mx[u] = v[u]; bool lbu = b[u]; b[u] = 1; if (l[u] != 0) { b[u] = b[u] && b[l[u]] && mx[l[u]] <= v[u]; mi[u] = min(mi[u], mi[l[u]]); mx[u] = max(mx[u], mx[l[u]]); } if (r[u] != 0) { b[u] = b[u] && b[r[u]] && mi[r[u]] >= v[u]; mi[u] = min(mi[u], mi[r[u]]); mx[u] = max(mx[u], mx[r[u]]); } // if (b[u] - lbu) // printf("+%lld\n", u); ans += b[u] - lbu; while (fa[u] != 0) { u = fa[u]; mi[u] = v[u]; mx[u] = v[u]; bool lbu = b[u]; b[u] = 1; if (l[u] != 0) { b[u] = b[u] && b[l[u]] && mx[l[u]] <= v[u]; mi[u] = min(mi[u], mi[l[u]]); mx[u] = max(mx[u], mx[l[u]]); } if (r[u] != 0) { b[u] = b[u] && b[r[u]] && mi[r[u]] >= v[u]; mi[u] = min(mi[u], mi[r[u]]); mx[u] = max(mx[u], mx[r[u]]); } // if (b[u] - lbu) // printf("+%lld\n", u); ans += b[u] - lbu; } } signed main() { //freopen("bst.in", "r", stdin); //freopen("bst.out", "w", stdout); int n = read(), q = read(); for (int i = 1; i <= n; i++) { fa[l[i] = read()] = i, fa[r[i] = read()] = i; } for (int i = 1; i <= n; i++) v[i] = read(); fa[0] = 0; dfs(1); while (q--) { upd(read(), read()); printf("%d\n", ans); } return 0; }