题目描述

Miranda 生活的城市有 N NN 个小镇,一开始小镇间没有任何道路连接。随着经济发现,小镇之间陆续建起了一些双向的道路但是由于经济不太发达,在建设过程中,会保证对于任意两个小镇,最多有一条路径能互相到达。有的时候 Miranda 会从某个小镇开始进行徒步旅行,每次出发前,她都想选择一个她能到达的最远的小镇作为终点,并且她在行走过程中是不会走回头路的,为了估算这次旅行的时间,她会需要你告诉她这次旅行的时间会是多少呢?可以假设通过每条道路都需要单位时间,并且 Miranda 不会在小镇停留。

输入格式

第一行一个整数 type \text{type}type,表示数据类型。
第二行两个整数 N NNQ QQ
接下来 Q QQ 行,每行先读入一个整数 t tt,若 t=1 t = 1t=1,则接下来读入两个整数 u uuv vv,表示小镇 u uu 与小镇 v vv 建立了一条新道路。若 t=2 t = 2t=2,读入一个整数 u uu,表示 Miranda 要开始一次从小镇 u uu 出发的旅行。

  • type=1 \text{type} = 1type=1,记 lastAns \text{lastAns}lastAns 表示最近一次 Miranda 旅行的时间,那么对于每次操作的 u uuu,v u, vu,v,都要异或上 lastAns \text{lastAns}lastAns
  • type=0 \text{type} = 0type=0,则不需要对数据进行处理。

输出格式

对于每次询问,输出 Miranda 能到达的最远的小镇的距离是多少。注意 Miranda 可能只能留在开始的小镇。

样例

样例输入

样例输出

数据范围与提示

对于 20% 20\%20% 的数据,N≤5000,Q≤10000 N \leq 5000, Q \leq 10000N5000,Q10000
对于 50% 50\%50% 的数据,N≤100000,Q≤200000 N \leq 100000, Q \leq 200000N100000,Q200000
对于另外 20% 20\%20% 的数据,type=0 \text{type} = 0type=0
对于 100% 100\%100% 的数据,N≤300000,Q≤500000,type∈{0,1} N \leq 300000, Q \leq 500000, \text{type} \in \{ 0, 1 \}N300000,Q500000,type{0,1},解密后的 u uuv vv 满足 1≤u,v≤N 1 \leq u, v \leq N1u,vN,且道路的修建会满足:每一时刻,都不存在 u,v u, vu,v 使得 u,v u, vu,v 之间能通过多种方式到达。

lct动态维护树的直径

性质1:一个点到树中的最远点一定是直径上的其中一个

性质2:合并两棵树的直径 枚举六种情况 分别枚举两边最远点的配对情况即可

 

分类: LCT-link cut tree

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论