Candyland 有一座糖果公园，公园里不仅有美丽的风景、好玩的游乐项目，还有许多免费糖果的发放点，这引来了许多贪吃的小朋友来糖果公园玩。

糖果公园的结构十分奇特，它由 n 个游览点构成，每个游览点都有一个糖果发放处，我们可以依次将游览点编号为 1 至 n。有 n−1条双向道路连接着这些游览点，并且整个糖果公园都是连通的，即从任何一个游览点出发都可以通过这些道路到达公园里的所有其它游览点。

糖果公园所发放的糖果种类非常丰富，总共 m 种，它们的编号依次为 1 至 m。每一个糖果发放处都只发放某种特定的糖果，我们用 ci 来表示 i 号游览点的糖果。

来到公园里游玩的游客都不喜欢走回头路，他们总是从某个特定的游览点出发前往另一个特定的游览点，并游览途中的景点，这条路线一定是唯一的。他们经过每个游览点，都可以品尝到一颗对应种类的糖果。

大家对不同类型的糖果的喜爱程度都不尽相同。根据游客们的反馈打分，我们得到了糖果的美味指数，第 i 种糖果的美味指数为 vi。另外，如果一位游客反复地品尝同一种类的糖果，他肯定会觉得有一些腻。根据量化统计，我们得到了游客第 i 次品尝某类糖果的新奇指数 wi，如果一位游客第 i 次品尝第 j 种糖果，那么他的愉悦指数 H 将会增加对应的美味指数与新奇指数的乘积，即 vjwi。这位游客游览公园的愉悦指数最终将是这些乘积的和。

当然，公园中每个糖果发放点所发放的糖果种类不一定是一成不变的。有时，一些糖果点所发放的糖果种类可能会更改（也只会是 m 种中的一种），这样的目的是能够让游客们总是感受到惊喜。

糖果公园的工作人员小 A 接到了一个任务，那就是根据公园最近的数据统计出每位游客游玩公园的愉悦指数。但数学不好的小 A 一看到密密麻麻的数字就觉得头晕，作为小 A 最好的朋友，你决定帮他一把。

输入格式

第一行包含三个正整数 n,m,q，分别表示游览点个数、糖果种类数和操作次数。

第二行包含 mm 个正整数 v1,v2,…,vm。

第三行包含 nn 个正整数 w1,w2,…,wn。

第四行到第 n+2 行，每行包含两个正整数 ai,bi，表示这两个游览点之间有路径可以直接到达。

第 n+3 行包含 n 个正整数 c1,c2,…,cn。

接下来 q 行，每行包含三个整数 t,x,y，表示一次操作：

若 t 为 0，则 1≤x≤n，1≤y≤m，表示编号为 x 的游览点发放的糖果类型改为 y；

若 t 为 1，则 1≤x,y≤n，表示对出发点为 x，终止点为 y 的路线询问愉悦指数。

输出格式

按照输入的先后顺序，对于每个 t 为 1 的操作输出一行，用一个正整数表示答案。

样例一

input

4 3 51 9 27 6 5 12 33 13 41 2 3 21 1 21 4 20 2 11 1 21 4 2

output

841312784

限制与约定

对于所有的数据，1≤vi,wi≤106，1≤ai,bi≤n，1≤ci≤m，w1,w2,…,wn 是非递增序列，即对任意 1<i≤n，满足 wi≤wi−1。

测试点编号	n	m	q	其它限制
1	≤20	≤20	≤20	无
2	≤2000	≤2000	≤2000
3	≤10000	≤10000	≤10000
4	≤80000	≤100	≤80000	没有修改操作；给出的图构成一条链
5	≤90000	≤100	≤90000
6	≤80000	≤80000	≤80000	没有修改操作
7	≤90000	≤90000	≤90000
8	≤80000	≤80000	≤80000	给出的图构成一条链
9	≤90000	≤90000	≤90000
10	≤100000	≤100000	≤100000	无

祝大家一遍 AC，求不虐萌萌哒测评机！

时间限制：8s

空间限制：512MB

 

 

真是卡OJ神题，我这道题加起来大概卡了UOJ有10min

树上带修莫队，按照DFS序分块或者王室联邦都行，好像王室联邦会更快

移动端点就是修改两条链，只要不断的往LCA爬，将路径上的点存在性取反就行了，不用讨论，但要记得LCA只翻转一次

记得排序的时候按照所属块排序，左右端点都是，不要写出右端点直接比较这种东西来了

 

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 #include