#include <bits/stdc++.h> #define int long long using namespace std; int l[200005], r[200005], fa[200005], mi[200005], mx[200005], v[200005], ans; bool b[200005]; 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, q; scanf("%lld %lld", &n, &q); for (int i = 1; i <= n; i++) { scanf("%lld %lld", &l[i], &r[i]); fa[l[i]] = i, fa[r[i]] = i; } for (int i = 1; i <= n; i++) scanf("%lld", &v[i]); fa[0] = 0; dfs(1); while (q--) { int k, x; scanf("%lld %lld", &k, &x); upd(k, x); printf("%lld\n", ans); } return 0; }