Tree
给定一棵有 n 个顶点的树,顶点编号为 1,2,…,n。顶点 i 的颜色为 ai。对于每个 i=2,…,n,有一条连接顶点 fai 与顶点 i 的边,它的颜色为 fci,长度为 fwi。
一条简单路径是好路径,当且仅当路径上的所有顶点颜色相同,并且路径上的所有边颜色相同。**顶点的共同颜色与边的共同颜色可以不同。**仅包含一个顶点的路径长度为 0。
接下来有 q 次操作。第 i 次操作把顶点 xi 的颜色改为 ci。在所有操作开始之前,以及每次操作完成之后,你都需要求出所有好路径中的最大长度。
输入格式
第一行包含两个正整数 n,q(1≤n,q≤2×105)。
第二行包含 n 个整数 a1,…,an(1≤ai≤n)。
第三行包含 n−1 个整数 fa2,…,fan(1≤fai<i)。
第四行包含 n−1 个整数 fc2,…,fcn(1≤fci≤n)。
第五行包含 n−1 个整数 fw2,…,fwn(0≤fwi≤109)。
接下来的 q 行中,第 i 行包含两个整数 xi,ci(1≤xi,ci≤n),表示把顶点 xi 的颜色改为 ci。
输入只有一组数据,不含测试组数。n=1 时,描述父亲、边色及边长的三行均没有整数。
输出格式
输出 q+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