P3168 - 水果姐逛水果街4

题目

P3168水果姐逛水果街4

限制 : 时间限制 : 10000 MS 空间限制 : 65536 KB

问题描述

连续三天都没有被难倒，水果姐心情很不错，第四天又来逛水果街。

今天换成了root来为难水果姐，root早早就来到了水果街等水果姐，因为他带来了帮手ZEALOT、xiaohao1和UncleGai。ZEALOT的魔法是把水果街变成有根树，xiaohao1的魔法是瞬间让某两家水果店之间的路径(包含端点)所有水果店的价格改为d。UncleGai的魔法是把以某家水果店为根的一颗子树的所有水果店的价格改为d，一边改，root一边提问，绝不给水果姐思考的时间！

同样还是n家水果店，编号为1~n，每家店能买水果也能卖水果，并且同一家店卖与买的价格一样。

一共有m个操作。

操作的格式为

0 x y d
1 x d
2 x y

如果操作类型是0，表示xiaohao1把第x家店到第y家店的路径上所有的水果店的价格全部改为d

如果操作类型是1，表示UncleGai把第x家店为根的子树上所有的水果店的价格全部改为d

如果操作类型是2，则表示要求水果姐从第x家店出发到第y家店，途中只能选一家店买一个水果，然后选一家店（可以是同一家店，但不能往回走）卖出去。并且输出最多可以赚多少钱。

输入格式

第一行两个整数n，k，表示有n家店根为k

下来n个正整数，表示每家店一个苹果的价格。

下来n-1行，每行两个整数x，y，表示第x家店和第y家店有一条边。

下来一个整数m，表示下来有m个操作。

下来有m行，每行表示一次操作。

输出格式

每行对应一个2类型的操作，输出一个整数，表示面对root的每次询问，水果姐最多可以赚到多少钱。

样例输入

7 1
1 2 3 4 5 6 7
1 2
2 3
2 4
1 5
5 6
6 7
6
2 7 1
2 7 3
0 4 5 8
2 7 1
1 2 10
2 7 4

样例输出

0
2
2
4

提示

0<=苹果的价格<=10^{8

1<=n<=2*10}5

1<=m<=10^5