P3519.第4题-树上最小公倍数追踪
题目内容
给定一棵以节点 1 为根的有 n 个节点的树，每个节点 i 有一个正整数权值 wi ，初始被涂成黑色或白色。你需要支持以下两种操作；
1.翻转节点 x 的颜色(黑色变白色，自色变黑色)；
2.查询从根节点 1 到节点 x 的路径上所有黑色节点的权值的最小公倍数(若路径上无黑色节点，则记为 1 )
【名词解释】
最小公倍数：最小公倍数是能够被给定整数集合中每个整数整除的最小正整数，记为 Icm 。
输入描述
第一行输入两个整数 n 和 q(1≦n,q≦2×105)，分别表示树的节点数量和操作数量。
第二行输入 n 个整数 w1,w2,...,wn(1≦wi≦100)，分别表示节点 1 到节点 n 的权值。
第三行输入一个长度为 n 、仅由字符 B 和 W 构成的字符串 c，其中 c1=B 表示节点 i 初始化为黑色，ci=W 表示初始化为白色。
接下来 n−1 行，每行输入两个整数 ui 和 vi(1≦ui,vi≦n;ui=vi) ，表示一条连接节点 ui 和节点 vi 的无向边，保证这 n 个节点构成一颗根为 1 的树。
接下来 q 行，每行输入两个整数 t 和 x(t∈1,2,1≦x≦n) ，表示一次操作。
1.当 t=1 时，执行翻转操作；
2.当 t=1 时，执行查询操作。
输出描述
对于每次查询操作，在一行中输出一个整数，表示对应路径上黑色节点权值的最小公倍数对 (109+7) 取模后的结果。
样例1
输入
5 5
2 3 4 5 6
BWBWB
1 2
1 3
3 4
3 5
2 4
1 3
2 4
1 1
2 5
输出
4
2
5
说明
在这个样例中，初始颜色为
-
节点 1→B ；
-
节点 2→W ；
-
节点 3→B ；
-
节点 4→W ；
-
节点 5→B 。
第一条查询 2 4 ：路径 1−3−4 上黑色节点为 1,3 ，权值分别为 2,4 ，lcm(2,4)=4，翻转节点 3 后第二次查询 2 4 ；路径上仅剩节点 1 为黑色，lcm(2)=2 ，再翻转节点 1 后第三次查询 2 5 ；路径 1−3−5 上仅有节点 5 为黑色，lcm(6)=6 。
