5560.树的直径

蛮不错的一道题目，你要利用树的性质分析出，你只需要维护上一次的树的直径的两个端点就好了

#include<iostream>using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int N = 6e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int qmi(int a,int b,int mod){int res=1;while(b){if(b&1)res=res*a%mod;b>>=1;a=a*a%mod;}return res;}int n,q,m;// int e[N],ne[N],w[N],h[N],idx;
// void add(int a,int b,int c){// e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
// }int dep[N];
int fa[N][22];int lca(int a,int b){if(dep[a]<dep[b])swap(a,b);for(int i=20;i>=0;--i)if(dep[fa[a][i]]>=dep[b])a = fa[a][i];if(a==b)return a;for(int i=20;i>=0;--i)if(fa[a][i]!=fa[b][i])a = fa[a][i],b =fa[b][i];return fa[a][0];}int dist(int a,int b){return dep[a]+dep[b]-2*dep[lca(a,b)];
}void solve()
{cin>>n;dep[2] = dep[3] = dep[4] = 2;dep[1] = 1;fa[1][0] = 0;fa[2][0] = fa[3][0] = fa[4][0] = 1;int tem = 4;int A = 2,B = 3;while(n--){int a;cin>>a;int b = ++tem,c = ++tem;fa[b][0] = a,fa[c][0] = a;dep[b] = dep[a]+1,dep[c] = dep[a]+1;for(int i=1;i<=20;i++)fa[b][i] = fa[fa[b][i-1]][i-1] ;for(int i=1;i<=20;i++)fa[c][i] = fa[fa[c][i-1]][i-1] ;int dista = dist(b,A),distb = dist(b,B);int dists = dist(A,B);//cout<<A<<" "<<B<<" "<<b<<" "<<dista<<" "<<distb<<" "<<dists<<"\n";if(dista<=dists&&distb<=dists){cout<<dists<<"\n";continue;}if(dista>dists&&dista>=distb){B=b;cout<<dista<<"\n";continue;}if(distb>dists){A=b;cout<<distb<<"\n";continue;}}}signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _;//cin>>_;_ = 1;while(_--)solve();return 0;
}