2243. Toptree

【题目描述】

你被派去完成一个任务，这个任务是必须A掉一个题，题目是这样的：你需要维护一个点带权的森林，支持加边、删边的操作，并且回答一些询问。

一开始，这个图是一张空图，没有边。

从现在开始，用节点u表示标号为u的节点。

操作共分为以下几种类型：

1 u v

表示在节点u与节点v之间连上一条无向边。

2 u v

表示删除节点u与节点v之间的无向边。

3 u x

将节点u的权值改为x.

4 u v

表示询问节点u与节点v之间的路径上的权值最小值.

5 w u v

表示询问以节点w为根时，节点u与节点v的最近公共祖先节点的标号。

6 w u

表示询问以节点w为根时，以节点u为根的子树的节点数。

7 w u

表示询问以节点w为根时，以节点u为根的子树权值最小值。

【输入格式】

第一行两个整数n,m，表示树上的总结点数，以及总的操作次数；

接下来一行n个整数，第i个整数为xi，表示节点i初始的权值；

接下来m行，依次表示m次操作。

【输出格式】

对于每一个操作类型为5,6,7的操作，输出一行一个整数，表示这次询问的答案。

【样例输入】

10 30

453693185 97417345 542909441 272416065 660418023 969737409 73086977 60587265 168796673 359459841

1 1 2

1 9 10

1 5 4

2 5 4

1 3 9

5 9 9 10

6 7 7

6 7 7

3 1 147640321

6 3 9

1 5 8

1 3 5

6 7 7

6 9 10

1 5 2

1 9 7

7 1 1

6 9 1

3 9 125258561

7 7 1

4 5 1

4 1 1

2 3 5

7 3 3

4 3 3

3 7 487083009

7 1 1

5 3 3 3

1 3 4

7 7 7

【样例输出】

9

1

1

2

1

1

60587265

1

147640321

97417345

147640321

73086977

542909441

60587265

3

125258561

【提示】

对于测试点1,2,3,4,5,6，保证n,m≤1000; 对于测试点7,8,9,10,11,12，保证只有操作1,2,3,4,5; 对于测试点13,14,15,16,保证没有操作7； 对于全部数据，1≤n,m≤100,000,保证所有操作均合法，且所有出现过的权值x均互不相同，且1≤x≤10^9。

【来源】

在此键入。