{"raw_statement":[{"iden":"background","content":"> _永远这么酷 永远永远这么酷_\\\n_像个冒险家一样 不断探着山顶的路_\\\n——《Hustle》\n\n张均好望着窗外，朱芝心走过来坐在他旁边，折了一架纸飞机飞出去。他对张均好说，要带着对未来的期待，往前走，别回头。\n\n正如 [命运](https://www.luogu.com.cn/problem/P6773) 所述，每个人的人生都是一棵树。它总在无限的随机与缘分中伸展，有的枝丫茂盛了，有些却也不可避免地枯萎。"},{"iden":"statement","content":"朱芝心用魔法得到了张均好的人生树。\n\n这是一棵 $n$ 个节点的树，节点 $i$ 上有权值 $w_i$。\n\n朱芝心想要观测 $m$ 次张均好的人生：\n\n设**当前**张均好人生树上的节点数量为 $s$。\n\n1. 输入四个整数 $u_1,v_1,u_2,v_2$。令 $u_1\\to v_1$ 的简单路径上**顺次组成**的数组为 $a$，$u_2\\to v_2$ 的简单路径上**顺次组成**的数组为 $b$。朱芝心认为张均好这两段人生的相似度是 $LRP(a,b)$，希望你求出它。保证 $1\\leq u_1,v_1,u_2,v_2 \\leq s$。\n\n2. 输入两个整数 $u,w'$。朱芝心观测到了张均好的另外一种可能，因此你需要新建一个点权为 $w'$ 的节点，编号为 $s+1$，建立一条 $(s+1,u)$ 的无向边，其中 $u\\leq s$。显然，此后 $s\\leftarrow s+1$。\n\n对于两个数组 $a,b$，设它们的相似度 $LRP(a,b)$ 表示最大的 $i$ 满足 $i\\leq \\min\\{|a|, |b|\\}$ 且**对于所有** $1\\leq j\\leq i$，都有 $b_j=a_j+j$。其中 $|a|$ 表示数组 $a$ 的长度。特殊地，若不存在这样的 $i$，则 $LRP(a,b) = 0$。\n"},{"iden":"input","content":"第一行三个正整数 $n,m,idx$，分别表示树的节点数量，操作数量和该测试点所在 Subtask 编号。对于样例，有 $idx = 0$。\n\n接下来一行 $n$ 个整数，第 $i$ 个整数表示 $w_i$，即点 $i$ 上的权值。\n\n接下来 $n - 1$ 行，每行两个正整数 $u_i,v_i$，表示有一条 $(u_i,v_i)$ 的无向边。\n\n接下来 $m$ 行，每行一个操作。每行第一个整数是 $opt$，后面的若干整数表示操作的具体内容。$opt=1$ 时表示是操作 $1$，$opt=2$ 时表示是操作 $2$。"},{"iden":"output","content":"对于每个操作 $1$，输出一行，表示当前询问的 $LRP(a, b)$。"},{"iden":"note","content":"### 样例解释\n\n对于样例一，第一个操作结束后，$w_{10}=10$，树如图所示：\n\n![](https://s1.ax1x.com/2023/04/26/p9MV9pV.png)\n\n- 对于第二个操作，第一条路径为 $3\\to 2\\to 4\\to 5$，故 $a=\\{2, 3, 4, 6\\}$，第二条路径为 $8\\to 7\\to 9\\to 10$，故 $b=\\{3, 5, 7, 10\\}$，由于 $3=2+1$，$5=3+2$，$7=4+3$，$10=6+4$，所以答案为 $4$；\n- 对于第三个操作，$a=\\{2, 3, 4, 5\\}$，$b=\\{3, 5, 7, 10\\}$，由于 $3=2+1$，$5=3+2$，$7=4+3$，$10\\ne 5+4$，所以答案为 $3$。\n\n对于样例二，初始的树如图所示：\n\n![](https://s1.ax1x.com/2023/04/26/p9MVZkR.png)\n\n\n| Subtask | $n \\le$ | $m \\le$ | 特殊性质 | 分值 |\n| :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |\n| Subtask 1 | $5000$ | $5000$ | 无 | $10$ |\n| Subtask 2 | $10^5$ | $5\\times{10}^4$ | A & B | $30$ |\n| Subtask 3 | $10^5$ | $5\\times{10}^4$ | B | $30$ |\n| Subtask 4 | $10^5$ | $5 \\times {10}^4$ | 无 | $20$ | \n| Subtask 5 | $10^5$ | $10^5$ | 无 | $10$ |\n\n特殊性质 A：$v_i=u_i+1$。\n\n特殊性质 B：保证无操作 2。\n\n对于 $100\\%$ 的数据，$1\\leq n,m\\leq 10^5$，$1\\leq w_i,w'\\leq 10^6$，$1\\leq u_i,v_i\\leq n$。  \n"}],"translated_statement":null,"sample_group":[["9 3 0\n7 3 2 4 6 5 5 3 7\n1 2\n2 3\n2 4\n4 5\n4 6\n1 7\n7 8\n7 9\n2 9 10\n1 3 5 8 10\n1 3 6 8 10","4\n3"],["13 5 0\n15 12 9 11 5 6 16 14 15 10 12 1 2\n7 8\n5 6\n2 9\n1 2\n4 5\n8 2\n9 10\n2 3\n10 11\n3 4\n3 13\n3 12\n1 1 6 7 11\n1 12 12 13 13\n2 1 10\n2 2 11\n1 14 14 15 15","6\n1\n1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}