lca求条
查看原帖
lca求条
836448
stylus楼主2025/1/12 02:00
#include<bits/stdc++.h>
#define int long long
using namespace std;
void read(int &x){
	x=0;bool f=0;char ch=getchar();
	while(ch>'9'||ch<'0'){
		if(ch=='-')f=1;
		ch=getchar();
	}do{x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}while(ch>='0'&&ch<='9');
	x=f?-x:x;
}
int n,f[101][15],dp[101],d[101],c,s,dd,bi[101];
string a,b,x,y;
map<string,int>p;
vector<int>v[101];
void gp(int k,int d){
    dp[k]=d;
    for(int i=1;(1<<i)<=dp[k];i++)f[k][i]=f[f[k][i-1]][i-1];
    for(int i:v[k])
        if(!dp[i])f[i][0]=k,gp(i,d+1);
    return;
}
int lca(int x,int y){
    if(dp[x]<dp[y])swap(x,y);
    int t=dp[x]-dp[y];
    for(int i=0;i<15;i++)
        if((1<<i)&t)c+=dp[x]-i-1,x=f[x][i];
    for(int i=14;i>=0;i--)
        if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i],s++;
    if(x==y)return x;
    s++;
    return f[x][0];
}
int gf(int x){
	return bi[x]!=x?bi[x]=gf(bi[x]):x;
}
signed main(){
	read(n),cin>>a>>b;
	for(int i=1;i<=101;i++)bi[i]=i;
	while(n--){
		cin>>x>>y;
		if(!p[x])p[x]=++c;
		if(!p[y])p[y]=++c;
		v[p[x]].push_back(p[y]),d[p[y]]=p[x];
		if(gf(p[x])!=gf(p[y]))bi[bi[p[x]]]=p[y];
	}for(int i=1;i<=c;i++)if(!d[i])s=i;
	if(p[a]==0||p[b]==0||gf(p[a])!=gf(p[b])){cout<<"NOT RELATED";return 0;}
	gp(s,1),c=0,s=0,dd=lca(p[a],p[b]);
	if(s>1)cout<<"COUSINS";
	else if(s){
		cout<<b<<" is the ";
		int t=dp[p[a]]-dp[dd];
		if(t==1)cout<<"sister";
		else{
			while(t>2)t--,cout<<"great-";
			cout<<"aunt";
		}cout<<" of "<<a;
	}else{
		cout<<b<<" is the ";
		int t=dp[p[a]]-dp[dd];
		while(t>2)t--,cout<<"great-";
		while(t>1)t--,cout<<"grand-";
		cout<<"mother of "<<a;
	}return 0;
}/*
MOTHER AA GGMOTHER BB SISTER AUNT COUSIN GMOTHER SISTER
1      2  3        4  5      7    8      6       5
7 AA BB
MOTHER AA
GGMOTHER BB
MOTHER SISTER
GMOTHER MOTHER
GMOTHER AUNT
AUNT COUSIN
GGMOTHER GMOTHER
1 2
3 4
1 5
6 1
6 7
7 8
3 6
*/
2025/1/12 02:00
加载中...