主题

主题

 
   

3083: 遥远的国度

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=3083

Description

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

问题是这样的:

遥远的国度有n个城市,这些城市之间由一些路连接且这些城市构成了一颗树。

这个国度有一个首都,我们可以把这个首都看做整棵树的根,但遥远的国度比较奇怪,首都是随时有可能变为另外一个城市的。

遥远的国度的每个城市有一个防御值,有些时候RapiD会使得某两个城市之间的路径上的所有城市的防御值都变为某个值。

RapiD想知道在某个时候,如果把首都看做整棵树的根的话,那么以某个城市为根的子树的所有城市的防御值最小是多少。

由于RapiD无法解决这个问题,所以他拦住了zcwwzdjn希望他能帮忙。但zcwwzdjn还要追杀sb的zhx,所以这个重大的问题就被转交到了你的手上。

Input

第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

对于每个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

2

3

4

提示

对于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。


个人解法:

学习了一下树链剖分的姿势。

某p猛然点醒我——树链剖分也是可以处理子树问题的。子树也是连续的一段区间。

至于换根的方法,我是参考别人的做法:http://blog.csdn.net/lcomyn/article/details/45718295

情况一   x=root,很显然此时应当查询整棵树。

情况二 lca(root,x)!=x ,此时直接查询x的子树即可,与换根无关。

情况三,lca(root,x)=x,此时我们应当查询与x相邻的节点中与root最近的点v在整棵树中的补集

本来做此题只是在做另外一题的时候看到别人的博客说这题是弱化版……于是先来做此题。倒也学会了一种维护子树与路径的方法。


代码如下:

https://code.csdn.net/snippets/2154648

 
 
评论