TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P5406
  • Problem
  • P5406遥远的国度
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 1s,512m
    Description

    zcwwzdjn在追杀十分sb的zhx,而zhx逃入了一个遥远的国度。当zcwwzdjn准备进入遥远的国度继续追杀时,守护神RapiD阻拦了zcwwzdjn的去路,他需要zcwwzdjn完成任务后才能进入遥远的国度继续追杀。

    问题是这样的:遥远的国度有n个城市,这些城市之间由一些路连接且这些城市构成了一颗树。这个国度有一个首都,我们可以把这个首都看做整棵树的根,但遥远的国度比较奇怪,首都是随时有可能变为另外一个城市的。遥远的国度的每个城市有一个防御值,有些时候RapiD会使得某两个城市之间的路径上的所有城市的防御值都变为某个值。RapiD想知道在某个时候,如果把首都看做整棵树的根的话,那么以某个城市为根的子树的所有城市的防御值最小是多少。由于RapiD无法解决这个问题,所以他拦住了zcwwzdjn希望他能帮忙。但zcwwzdjn还要追杀sb的zhx,所以这个重大的问题就被转交到了你的手上。

    Input Format

    第1行两个整数n m,代表城市个数和操作数。
    第2行至第n行,每行两个整数 u v,代表城市u和城市v之间有一条路。
    第n+1行,有n个整数,代表所有点的初始防御值。
    第n+2行一个整数 id,代表初始的首都为id。
    第n+3行至第n+m+2行,首先有一个整数opt,如果opt=1,接下来有一个整数id,代表把首都修改为id;如果opt=2,接下来有三个整数p1 p2 v,代表将p1 p2路径上的所有城市的防御值修改为v;如果opt=3,接下来有一个整数 id,代表询问以城市id为根的子树中的最小防御值。

    Output Format

    对于每个opt=3的操作,输出一行代表对应子树的最小点权值。

    Sample Input

    3 7
    1 2
    1 3
    1 2 3
    1
    3 1
    2 1 1 6
    3 1
    2 2 2 5
    3 1
    2 3 3 4
    3 1

    Sample Output

    1
    2
    3
    4

    Hint

    对于20%的数据,n<=1000 m<=1000。

    对于另外10%的数据,n<=100000,m<=100000,保证修改为单点修改。

    对于另外10%的数据,n<=100000,m<=100000,保证树为一条链。

    对于另外10%的数据,n<=100000,m<=100000,没有修改首都的操作。

    对于100%的数据,n<=100000,m<=100000,0<所有权值<=2^31。