当前位置：网站首页>loj 6038「雅礼集训 2017 Day5」远行

loj 6038「雅礼集训 2017 Day5」远行

2022-08-08 14:02:00 【51CTO】


​ ​http://www.elijahqi.win/archives/3236​​​
题目描述

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

输入格式

第一行一个整数 type \text{type}type，表示数据类型。
第二行两个整数 N NN、Q QQ。
接下来 Q QQ 行，每行先读入一个整数 t tt，若 t=1 t = 1t=1，则接下来读入两个整数 u uu、v 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 uu 或 u,v u, vu,v，都要异或上 lastAns \text{lastAns}lastAns。
若 type=0 \text{type} = 0type=0，则不需要对数据进行处理。
输出格式

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

样例

样例输入

0
5 10
1 4 5
2 3
2 5
2 1
1 5 3
1 1 4
2 3
2 5
1 5 2
2 1
样例输出

0
1
0
3
2
3
数据范围与提示

对于 20% 20\%20% 的数据，N≤5000,Q≤10000 N \leq 5000, Q \leq 10000N≤5000,Q≤10000；
对于 50% 50\%50% 的数据，N≤100000,Q≤200000 N \leq 100000, Q \leq 200000N≤100000,Q≤200000；
对于另外 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 }N≤300000,Q≤500000,type∈{0,1}，解密后的 u uu、v vv 满足 1≤u,v≤N 1 \leq u, v \leq N1≤u,v≤N，且道路的修建会满足：每一时刻，都不存在 u,v u, vu,v 使得 u,v u, vu,v 之间能通过多种方式到达。

lct动态维护树的直径

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

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

      
      

       
       #include<cstdio>
       
       
#include<cctype>
       
       
#include<algorithm>
       
       
using namespace std;
       
       
inline char gc(){
       
       
    static char now[1<<16],*S,*T;
       
       
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
       
       
    return *S++;
       
       
}
       
       
inline int read(){
       
       
    int x=0,f=1;char ch=gc();
       
       
    while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();}
       
       
    while(isdigit(ch)) x=x*10+ch-'0',ch=gc();
       
       
    return x*f;
       
       
}
       
       
const int N=3e5+10;bool rev[N];
       
       
int fa1[N],size[N],fa[N],c[N][2],d1[N],d2[N],type,n,q[N],top,Q,ans;
       
       
inline int find(int x){
       
       
    while(fa1[x]!=x) x=fa1[x]=fa1[fa1[x]];return x;
       
       
}
       
       
inline bool isroot(int x){
       
       
    return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;
       
       
}
       
       
inline void update(int x){
       
       
    size[x]=size[c[x][0]]+size[c[x][1]]+1;
       
       
}
       
       
inline void rotate(int x){
       
       
    int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1;
       
       
    if (!isroot(y)) c[z][c[z][1]==y]=x;
       
       
    fa[c[x][r]]=y;fa[y]=x;fa[x]=z;
       
       
    c[y][l]=c[x][r];c[x][r]=y;update(y);update(x);
       
       
}
       
       
inline void pushdown(int x){
       
       
    if(!rev[x]) return;int l=c[x][0],r=c[x][1];
       
       
    rev[x]^=1;rev[l]^=1;rev[r]^=1;swap(c[x][0],c[x][1]);
       
       
}
       
       
inline void splay(int x){
       
       
    q[top=1]=x;for (int i=x;!isroot(i);i=fa[i]) q[++top]=fa[i];
       
       
    while(top) pushdown(q[top--]);
       
       
    while(!isroot(x)){
       
       
        int y=fa[x],z=fa[y];
       
       
        if (!isroot(y)){
       
       
            if(c[y][0]==x^c[z][0]==y) rotate(x);else rotate(y);
       
       
        }rotate(x);
       
       
    }
       
       
}
       
       
inline void access(int x){
       
       
    for (int t=0;x;t=x,x=fa[x]) 
       
       
    splay(x),
       
       
    c[x][1]=t,
       
       
    update(x);
       
       
}
       
       
inline void makeroot(int x){
       
       
    access(x);splay(x);rev[x]^=1;
       
       
}
       
       
inline int calc(int x,int y){
       
       
    makeroot(x);
       
       
    access(y);splay(y);
       
       
    return size[c[y][0]];
       
       
}
       
       
inline void link(int x,int y){
       
       
    makeroot(x);fa[x]=y;x=find(x);y=find(y);int mx=-1,now1,now2,t;
       
       
    if((t=calc(d1[x],d2[x]))>mx) mx=t,now1=d1[x],now2=d2[x];
       
       
    if((t=calc(d1[y],d2[y]))>mx) mx=t,now1=d1[y],now2=d2[y];
       
       
    if((t=calc(d1[x],d1[y]))>mx) mx=t,now1=d1[x],now2=d1[y];
       
       
    if((t=calc(d1[x],d2[y]))>mx) mx=t,now1=d1[x],now2=d2[y];
       
       
    if((t=calc(d2[x],d1[y]))>mx) mx=t,now1=d2[x],now2=d1[y];
       
       
    if((t=calc(d2[x],d2[y]))>mx) mx=t,now1=d2[x],now2=d2[y];
       
       
    fa1[x]=y;d1[y]=now1;d2[y]=now2;
       
       
}
       
       
int main(){
       
       
    freopen("loj6038.in","r",stdin);
       
       
    type=read();int last_ans=0;
       
       
    n=read();Q=read();
       
       
    for (int i=1;i<=n;++i) d1[i]=d2[i]=fa1[i]=i,size[i]=1;
       
       
    for (int i=1;i<=Q;++i){static int op,u,v;op=read();
       
       
        if (op==1) u=read()^last_ans,v=read()^last_ans,link(u,v);
       
       
        else{
       
       
            v=read()^last_ans;u=find(v);
       
       
            printf("%d\n",ans=max(calc(v,d1[u]),calc(v,d2[u])));
       
       
        }last_ans=ans*type;
       
       
    }
       
       
    return 0;
       
       
}
      
      

      
      
    
       
       
  • 1.
    • 
       
       
  • 2.
    • 
       
       
  • 3.
    • 
       
       
  • 4.
    • 
       
       
  • 5.
    • 
       
       
  • 6.
    • 
       
       
  • 7.
    • 
       
       
  • 8.
    • 
       
       
  • 9.
    • 
       
       
  • 10.
    • 
       
       
  • 11.
    • 
       
       
  • 12.
    • 
       
       
  • 13.
    • 
       
       
  • 14.
    • 
       
       
  • 15.
    • 
       
       
  • 16.
    • 
       
       
  • 17.
    • 
       
       
  • 18.
    • 
       
       
  • 19.
    • 
       
       
  • 20.
    • 
       
       
  • 21.
    • 
       
       
  • 22.
    • 
       
       
  • 23.
    • 
       
       
  • 24.
    • 
       
       
  • 25.
    • 
       
       
  • 26.
    • 
       
       
  • 27.
    • 
       
       
  • 28.
    • 
       
       
  • 29.
    • 
       
       
  • 30.
    • 
       
       
  • 31.
    • 
       
       
  • 32.
    • 
       
       
  • 33.
    • 
       
       
  • 34.
    • 
       
       
  • 35.
    • 
       
       
  • 36.
    • 
       
       
  • 37.
    • 
       
       
  • 38.
    • 
       
       
  • 39.
    • 
       
       
  • 40.
    • 
       
       
  • 41.
    • 
       
       
  • 42.
    • 
       
       
  • 43.
    • 
       
       
  • 44.
    • 
       
       
  • 45.
    • 
       
       
  • 46.
    • 
       
       
  • 47.
    • 
       
       
  • 48.
    • 
       
       
  • 49.
    • 
       
       
  • 50.
    • 
       
       
  • 51.
    • 
       
       
  • 52.
    • 
       
       
  • 53.
    • 
       
       
  • 54.
    • 
       
       
  • 55.
    • 
       
       
  • 56.
    • 
       
       
  • 57.
    • 
       
       
  • 58.
    • 
       
       
  • 59.
    • 
       
       
  • 60.
    • 
       
       
  • 61.
    • 
       
       
  • 62.
    • 
       
       
  • 63.
    • 
       
       
  • 64.
    • 
       
       
  • 65.
    • 
       
       
  • 66.
    • 
       
       
  • 67.
    • 
       
       
  • 68.
    • 
       
       
  • 69.
    • 
       
       
  • 70.
    • 
       
       
  • 71.
    • 
       
       
  • 72.
    • 
       
       
  • 73.
    • 
       
       
  • 74.
    • 
       
       
  • 75.
    • 
       
       
  • 76.
    • 
       
       
  • 77.
    • 
       
       
  • 78.
    • 
       
       
  • 79.
    • 
       
       
  • 80.
    • 
       
       
  • 81.
    • 
       
       
  • 82.
    • 
       
       
  • 83.
    • 
       
       
  • 84.
    •


原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15744996/5555446

边栏推荐

猜你喜欢

随机推荐