关键词：
用合并直径的定理，并查集维护每棵树的直径
主要是看看过了这么久自己的lct有没有变残废2333（1A还行
#include<stdio.h>
int ch[300010][2],fa[300010],r[300010],siz[300010],sfa[300010],d1[300010],d2[300010];
void pushup(int x){siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;}
void swap(int&a,int&b){a^=b^=a^=b;}
void rev(int x){
r[x]^=1;
swap(ch[x][0],ch[x][1]);
}
void pushdown(int x){
if(r[x]){
if(ch[x][0])rev(ch[x][0]);
if(ch[x][1])rev(ch[x][1]);
r[x]=0;
}
}
bool isrt(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
void rot(int x){
int y,z,f,B;
y=fa[x];
z=fa[y];
f=(ch[y][0]==x);
B=ch[x][f];
fa[x]=z;
fa[y]=x;
if(B)fa[B]=y;
ch[x][f]=y;
ch[y][f^1]=B;
if(ch[z][0]==y)ch[z][0]=x;
if(ch[z][1]==y)ch[z][1]=x;
pushup(y);
pushup(x);
}
void gao(int x){
if(fa[x])gao(fa[x]);
pushdown(x);
}
void splay(int x){
gao(x);
int y,z;
while(!isrt(x)){
y=fa[x];
z=fa[y];
if(!isrt(y))rot((ch[z][0]==y&&ch[y][0]==x)||(ch[z][1]==y&&ch[y][1]==x)?y:x);
rot(x);
}
}
void access(int x){
int y=0;
while(x){
splay(x);
ch[x][1]=y;
pushup(x);
y=x;
x=fa[x];
}
}
void makert(int x){
access(x);
splay(x);
rev(x);
}
void link(int x,int y){
makert(x);
fa[x]=y;
}
int query(int x,int y){
makert(x);
access(y);
splay(y);
return siz[y]-1;
}
int getfa(int x){return(x==sfa[x])?x:(sfa[x]=getfa(sfa[x]));}
int max(int a,int b){return a>b?a:b;}
int main(){
int type,n,m,i,j,x,y,mx,p1,p2,las,tmp,t[4];
scanf("%d%d%d",&type,&n,&m);
for(i=1;i<=n;i++){
siz[i]=1;
sfa[i]=d1[i]=d2[i]=i;
}
las=0;
while(m--){
scanf("%d",&i);
if(i==1){
scanf("%d%d",&x,&y);
if(type==1){
x^=las;
y^=las;
}
link(x,y);
x=getfa(x);
y=getfa(y);
t[0]=d1[x];
t[1]=d2[x];
t[2]=d1[y];
t[3]=d2[y];
mx=0;
for(i=0;i<3;i++){
for(j=i+1;j<4;j++){
tmp=query(t[i],t[j]);
if(tmp>mx){
mx=tmp;
p1=t[i];
p2=t[j];
}
}
}
d1[x]=p1;
d2[x]=p2;
sfa[y]=x;
}else{
scanf("%d",&x);
if(type==1)x^=las;
y=getfa(x);
las=max(query(x,d1[y]),query(x,d2[y]));
printf("%d
",las);
}
}
}
hdu6038
题意：给出a,b序列，求多少种f序列，f序列是f(i)=b(f(ai)).思路：从例子出发3 4 2 0 1 0 2 31 可以知道a序列有个长度为3的循环节，即a[0]=2,a[1]=0,a[2]=1,b序列有长度为1... 查看详情
hdu6038function（思维+寻找循环节）
http://acm.hdu.edu.cn/showproblem.php?pid=6038题意：给出两个序列，一个是0~n-1的排列a，另一个是0~m-1的排列b，现在求满足的f的个数。 思路：先看一下样例吧：对于这组数来说，假如我们先指定了f（0）对应的在b中的值，那么根据第2... 查看详情
(stat2008/stat4038/stat6014/stat6038)
REGRESSIONMODELLING(STAT2008/STAT4038/STAT6014/STAT6038)Assignment1forSemester1,2019INSTRUCTIONS:Thisassignmentisworth15%ofyouroverallmarksforthiscourse.PleasesubmityourassignmentonWattle.WhenuploadingtoWattleyoumustsubmitthefollowing,combinedintoasingledocument:1.Yourassignment/reportinapdfdocument... 查看详情
2017多校第一套&&hdu6038思维数学
链接 http://acm.hdu.edu.cn/showproblem.php?pid=6038 题意： 给你一个a序列，代表0到n-1的排列；一个b序列代表0到m-1的排列。问你可以找出多少种函数关系f，f的定义域内的i都满足f(i)=b[f(a[i])]; 分析：这个主要是找循环节循环... 查看详情
6038function数学(循环节)
题意:给出两个排列a[i]:0~n-1和b[i]:0~m-1.问有多少种F,满足F[i]=b[F[a[i]]?n,m<=1e5.i:012a[i]:102f[0]=b[f[1]]f[1]=b[f[0]],f[2]=b[f[2]]如果知道循环节上任意一个的f值则循环节上剩下的f值也就确定了.假如f[i]所在循环节长度为L,f[i]等于某个b[x].因为:... 查看详情
hdu6038-function-数学+思维-2017多校team01
学长讲座讲过的，代码也讲过了，然而，当时上课没来听，听代码的时候也一脸o((⊙﹏⊙))o我的妈呀，语文不好是硬伤，看题意看了好久好久好久(死一死)。。。数学+思维题，代码懂了，也能写出来，但是还是有一点不懂，明天... 查看详情
leetcode6038.向表达式添加括号后的最小结果(代码片段)
文章目录一、题目1、题目描述2、基础框架3、原题链接二、解题报告1、思路分析2、时间复杂度3、代码详解三、本题小知识四、加群须知一、题目1、题目描述 给你一个下标从0开始的字符串expression，格式为“+”，... 查看详情
csharped5b6038-9303-4c03-a6cd-8464ca11cad6(代码片段)
查看详情
loj558&loj2011
loj2011题意：一棵树有两种操作1.选定一个点且这个点的权值随着时间的增加而增加1 2.查询一条路径上点的个数和权值大于C的个数题解：刚开始没想到离线的做法认为可以大力线段树n(logn)^3然而显然... 查看详情
loj10195.「一本通6.1练习2」转圈游戏（loj2608）(代码片段)
思路： 简单的数学题。#include<cstdio>#include<iostream>usingnamespacestd;longlongquickpow(longlonga,longlongb,longlongp)longlongres=1;while(b)if(b&1)res=res*a%p;a=a*a%p;b>>=1;returnres 查看详情
loj#124.除数函数求和
链接：https://loj.ac/problem/124 就是筛一下积性函数。 #include<bits/stdc++.h>#definelllonglong#definemaxn10000000#defineha1000000007usingnamespacestd;intzs[maxn/10],t=0;intlow[maxn+5];intf[maxn+5]; 查看详情
loj#125.除数函数求和
link: https://loj.ac/problem/125 分块calc即可。 #include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintha=998244353;intn,ans[3];inlineintadd(intx,inty)x+=y;returnx>=ha?x 查看详情
loj#6185.烷基计数
link: https://loj.ac/problem/6185 随便DP一下就好了(我最近怎么越来越懒了2333)注意当子树大小有相同的时候需要用可重组合。。 #include<bits/stdc++.h>#definelllonglong#definemaxn405usingnamespacestd;constintha=1000000007;int 查看详情
[loj]数列分块(代码片段)
数列分块入门1https://loj.ac/problem/6277区间加+单点查询#include<iostream>#include<cstdio>#include<cmath>usingnamespacestd;constintN=5e4+10;#definegcgetchar()inlineintread()intx=0;charc=gc;while( 查看详情
loj6044
题意(n)个点的完全图，(1)为根，深度为(1)，求深度为奇数的点恰好(m)个的生成树个数做法比较巧妙的一点是把树看成二分图，然后就是(K_m,n-m)的生成树个数了 查看详情
59:loj#10215(代码片段)
$des$https://loj.ac/problem/10215$sol$exgcd检查$code$#include<iostream>#include<cstdlib>#include<algorithm>#include<cstring>#include<cstdio>usingnamespacestd;#definegcgetch 查看详情
loj10139.「一本通4.5练习1」树上操作（loj2125.「haoi2015」树上操作）(代码片段)
思路： 第二遍dfs时记录end[x]为在结点序列中以x为根的子树最后访问的节点，写个线段树标记下传即可。与值有关的数据注意longlong#include<cstdio>#include<iostream>#include<vector>#include<cmath>#include<string>usingnamespa... 查看详情
loj#6281.数列分块入门5(代码片段)
...方，区间求和。 题解： 怎么说...这道题loj的数据有点水。 和bzoj花神游历各国是一样的...但是loj没有卡掉不完全优化的代码。 基础操作就不说了（同分块4），主要讲优化吧： 查看详情