网站空间 阿里云,免费的素材网站,网站备案多少岁,有限公司企业网站建设方案蛮不错的一道题目#xff0c;你要利用树的性质分析出#xff0c;你只需要维护上一次的树的直径的两个端点就好了 #includeiostreamusing namespace std;
using ll long long;
using pii pairint,int;
const int N 6e510;
const int inf 0x3f3f3f3f;
cons… 蛮不错的一道题目你要利用树的性质分析出你只需要维护上一次的树的直径的两个端点就好了 #includeiostreamusing namespace std;
using ll long long;
using pii pairint,int;
const int N 6e510;
const int inf 0x3f3f3f3f;
const int mod 1e97;
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 res1;while(b){if(b1)resres*a%mod;b1;aa*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 i20;i0;--i)if(dep[fa[a][i]]dep[b])a fa[a][i];if(ab)return a;for(int i20;i0;--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()
{cinn;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;cina;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 i1;i20;i)fa[b][i] fa[fa[b][i-1]][i-1] ;for(int i1;i20;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);//coutA B b dista distb dists\n;if(distadistsdistbdists){coutdists\n;continue;}if(distadistsdistadistb){Bb;coutdista\n;continue;}if(distbdists){Ab;coutdistb\n;continue;}}}signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _;//cin_;_ 1;while(_--)solve();return 0;
}
