#P18712. Tree

    ID: 18048 传统题 5000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF2900省选/NOI-树形 DP动态 DP树链剖分维护 DP线段树维护转移有序多重集合

Tree

Tree

给定一棵有 nn 个顶点的树,顶点编号为 1,2,…,n1,2,\ldots,n。顶点 ii 的颜色为 aia_i。对于每个 i=2,…,ni=2,\ldots,n,有一条连接顶点 faifa_i 与顶点 ii 的边,它的颜色为 fcifc_i,长度为 fwifw_i。

一条简单路径是好路径,当且仅当路径上的所有顶点颜色相同,并且路径上的所有边颜色相同。**顶点的共同颜色与边的共同颜色可以不同。**仅包含一个顶点的路径长度为 00。

接下来有 qq 次操作。第 ii 次操作把顶点 xix_i 的颜色改为 cic_i。在所有操作开始之前,以及每次操作完成之后,你都需要求出所有好路径中的最大长度。

输入格式

第一行包含两个正整数 n,qn,q(1≤n,q≤2×1051\le n,q\le 2\times10^5)。

第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n(1≤ai≤n1\le a_i\le n)。

第三行包含 n−1n-1 个整数 fa2,…,fanfa_2,\ldots,fa_n(1≤fai<i1\le fa_i<i)。

第四行包含 n−1n-1 个整数 fc2,…,fcnfc_2,\ldots,fc_n(1≤fci≤n1\le fc_i\le n)。

第五行包含 n−1n-1 个整数 fw2,…,fwnfw_2,\ldots,fw_n(0≤fwi≤1090\le fw_i\le10^9)。

接下来的 qq 行中,第 ii 行包含两个整数 xi,cix_i,c_i(1≤xi,ci≤n1\le x_i,c_i\le n),表示把顶点 xix_i 的颜色改为 cic_i。

输入只有一组数据,不含测试组数。n=1n=1 时,描述父亲、边色及边长的三行均没有整数。

输出格式

输出 q+1q+1 行。

第一行输出任何操作开始之前的好路径最大长度;此后每次操作对应一行,输出这次操作完成后的好路径最大长度。

样例

样例输入

5 5
5 4 3 4 5
1 2 3 1
2 2 2 2
4 9 2 6
2 5
4 5
5 4
3 5
2 1

样例输出

6
10
10
4
15
2