#P4234. 带Link、Cut树上路径k小值

    ID: 2563 传统题 8000ms 512MiB 尝试: 7 已通过: 3 难度: 10 上传者: 标签>难度分类NOI/NOI+/CTS数据结构Link-Cut Tree根号分块可持久化线段树树上版本差分树算法树上倍增线段树上二分CF3100

带Link、Cut树上路径k小值

带 Link、Cut 的树上路径第 k 小值

题目描述

FUS 公司是一家大型网络公司,总共拥有n台服务器。每一台服务器都有一个limit值,表示这台服务器的最大连接限制。在这n台服务器中,只有n-1条光纤线路连接,保证任意两台服务器可以互相通信。随着公司的发展、用户的增加,服务器的负担越来越重,一些服务器无法胜任任务,一些光纤也趋于老化。

因此FUS常常对服务器进行一些调整:

  • 更新操作:选中两个服务器x、y,用一条新的光纤连接它们,形成一个环。这时环上“加入时间”最早的光纤会被断开废弃。

  • 修改操作:修改一个服务器的limit值,可以增大或减小,以胜任业务。

在用户访问时,FUS会智能选择服务器的处理。如果用户访问的内容在x到y服务器的路径上,FUS会自动分配一个k值,令x到y路径上limit值第k小的服务器服务用户。

FUS希望你能帮帮他实现这些功能。 (简化版:动态维护关于加入时间的最大生成树,带点权修改,多次询问树上给定两点间路径k小值)

输入格式

第一行两个整数 n,mn,m,分别表示服务器数量和操作次数。

第2行n个整数,limit[1]到limit[n],0≤limiti≤1060\le\mathrm{limit}_i\le10^6,表示n个服务器的初始连接限制。

接下来 n−1n-1 行,每行两个整数 u,vu,v,表示一条连接服务器 u,vu,v 的光纤。这些光纤的输入顺序就是它们从早到晚的加入顺序。

接下来m行,每行3个整数k、x、y,表示一个操作,总共有3种:

  1. k=−1k=-1,1≤x,y≤n1\le x,y\le n,xx不等于yy,表示更新操作,连接x、yx、y光纤,并断开环上最早加入的光纤;
  2. k=0k=0,1≤x≤n1\le x\le n,0≤y≤1060\le y\le10^6,表示修改操作,将xx服务器的limit值修改为yy;
  3. 1≤k≤n1\le k\le n,1≤x,y≤n1\le x,y\le n,xx不等于yy,表示一个用户访问的内容在xx到yy服务器的路径上,要求取limit值第kk小的服务器服务用户。 对于第3种操作,保证kk不超过xx到yy路径上的服务器数,也就是保证存在第 kk 小的连接限制值。路径包含两个端点,相同的限制值按各自所在的服务器分别计数。

输出格式

对于每次查询输出一行一个整数,表示xx到yy路径上limit值第kk小的服务器的limit值。

样例 #1

样例输入 #1

10 4
1 2 3 4 5 6 7 8 9 10
1 2
2 3
2 4
2 5
3 6
3 7
1 8
8 9
9 10
-1 1 10
0 2 100002
2 2 8
3 6 5

样例输出 #1

8
6

样例说明

第1个操作,更新操作,用光纤连接了1、10服务器,断开了1、8服务器之间的光纤。

第2个操作,修改操作,将2的limit值从2修改成了100002。

第3个操作,2到8之间的路径为2-1-10-9-8,limit值分别为100002、1、10、9、8,因此第2小的limit值为8。

第4个操作,6到5之间的路径为6-3-2-5,limit值分别为6、3、100002、5,因此第3小的limit值为6。

数据规模与约定

本题有4种类型的数据。

类型一(10%):n=m=1000n=m=1000

类型二(20%):n=m=50000n=m=50000,0≤k≤n0\leq k\leq n(即不存在更新操作)

类型三(30%):n=m=50000n=m=50000,保证询问的路径长度之和小于10810^8。

类型四(40%):n=m=100000n=m=100000

对于100%的数据,满足2≤n,m≤100 0002\leq n,m\leq 100\,000、每台服务器的连接限制值始终在 [0,106][0,10^6]。