C · 午枫的LCA · GESP考级

题目描述

有两棵树 $A$ 和 $B$ ，每棵树都有 $n$ 个节点。每棵树上的节点编号都是从 $1$ 到 $n$ ，树 $A$ 的第 $i$ 个节点的权值为 $a_i$ ，树 $B$ 的第 $i$ 个节点的权值为 $b_i$ 。每棵树的根节点都是 $1$ 号节点。 现在这两颗树上都有 $m$ 个节点被标记，且两棵树上被标记的节点编号相同，都为 $x_1,x_2,\dots,x_k$ 。 请回答 $m$ 个问题，对于每个 $i$ $(1\leq i\leq m)$ ，若恰好只删除编号 $x_i$ 的标记，树 $A$ 中剩余被标记的节点的最近公共祖先（$LCA$）的权值是否大于树 $B$ 中剩余被标记的节点的 $LCA$ 的权值，若大于，则输出 YES ；否则输出 NO 。

第一行输入两个正整数 $n,m$ $(2\leq k\leq n \leq 2\times10^5)$ ，分别表示树上节点个数和被标记的节点个数。 第二行输入 $n$ 个整数 $a_i$ $(0\leq a_i\leq 10^9)$ ，表示树 $A$ 中第 $i$ 个节点的权值。 第三行输入 $n-1$ 个整数 $ap_i$ $(1\leq ap_i\leq i)$，表示树 $A$ 中第 $i+1$ 个节点的父亲节点。 第四行输入 $n$ 个整数 $b_i$ $(0\leq b_i\leq 10^9)$ ，表示树 $B$ 中第 $i$ 个节点的权值。 第五行输入 $n-1$ 个整数 $bp_i$ $(1\leq bp_i\leq i)$，表示树 $B$ 中第 $i+1$ 个节点的父亲节点。 第六行输入 $m$ 个正整数 $x_i$ $(1\leq x_i\leq n)$ ，表示被标记的节点编号。

输出共 $k$ 行，对于每个 $x_i$ ，若恰好只删除编号 $x_i$ 的标记，树 $A$ 中剩余被标记的节点的 $LCA$ 的权值是否大于树 $B$ 中剩余被标记的节点的 $LCA$ 的权值，若大于，则输出 YES ；否则输出 NO 。

输入 #1

输出 #1

YES
NO
NO