Hdu 4409 Family Name List (LCA 家谱 STL 2012金华网赛)

素颜马尾好姑娘i 2022-08-24 14:18 192阅读 0赞

题意：给出一个家谱，处理三种操作。

（1）L重新打印家谱，同一代的人按照升序；  
（2）b name 输出name的亲兄弟有多少个？  
（3）c name1 name2输出name1和name2 的最近公共祖先。  
注意（3）：如果最近公共祖先是name1或者name2，那么要输出其父亲。（因为自己不能是自己的祖先。。）

#pragma warning(disable:4786)
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <set>
    #include <map>
    #include <string>
    using namespace std;
    
    const int N=60005;
    map<string,int> mp;
    set<string> st[N];
    
    int father_id[N];     //father_id[a]=b:名字前有a个点的人输入id为b
    int Num_bro[N];       //记录i的兄弟数
    int father[N];        //记录i的父节点
    char data[N][63];     //记录原始数据
    int n,curID;
    
    int F[N],B[N],RMQ[N*3][32];
    int ID[N];
    
    void init ()
    {
    	curID=0;
    	memset(father,0,sizeof(father));
    	memset(Num_bro,0,sizeof(Num_bro));
    	mp.clear();
    	Num_bro[0] = 1;   //这里很容易错，注意要初始化
    	for (int i=0;i<=n;i++)
    		st[i].clear();
    }
    
    void Input ()
    {
    	int j,Num_dots;
    	for (int i=0;i<n;i++)
    	{
    		string str;
    		scanf("%s",data[i]);
    		Num_dots=0;
    		for (j=0;j<strlen(data[i]);j++)     //找点的个数
    			if (data[i][j] == '.')
    				Num_dots++;
    			else break;
    
    		father_id[Num_dots]=i;              //用来找父子关系
    		for (;j<strlen(data[i]);j++)        //将该名字赋值给临时变量
    			str+=(data[i][j]);
    
    		mp[str]=i;                          //建立映射关系
    		if (Num_dots)
    		{
    			st[father_id[Num_dots-1]].insert(str);
    			father[i] = father_id[Num_dots - 1];  //记录该节点的父亲节点
    		}
    	}
    }
    
    void Cal ()
    {
    	set<string>::iterator it;
    	for (int i=0;i<n;i++)
    		for (it=st[i].begin();it!=st[i].end();it++)
    		{
    			int tmp = mp[*it];
    			Num_bro[tmp] = st[i].size();   //统计兄弟数量
    		}
    }
    
    void DFS (int u,int dep)
    {
        F[++curID]=u;
        B[curID]=dep;
        ID[u]=curID;      //在循环外,只有第一次被访问时被赋值
        set<string>::iterator it;
        for (it = st[u].begin();it != st[u].end();it++)
    	{
            int v = mp[*it];
            DFS(v,dep+1);
            F[++curID]=u;
            B[curID]=dep;
        }
    }
    
    void init_RMQ ()      //rmq的初始化
    {
    	int i,j,x,y;
    	for (i=1;i<=curID;i++)
    		RMQ[i][0]=i;
    	for (j=1;(1<<j)<=curID;j++)
    		for (i=1;i+(1<<j)-1<=curID;i++)
    		{
    			x=RMQ[i][j-1];
    			y=RMQ[i+(1<<(j-1))][j-1];
    			RMQ[i][j]=B[x]<B[y]?x:y;
    		}
    }
    
    void Dfs_out (int u)   //顺序输出，这里set直接排序了
    {
    	int v;
    	set<string>::iterator it;
    	for (it=st[u].begin();it != st[u].end();it++)
    	{
    		v = mp[*it];
    		printf("%s\n",data[v]);
    		Dfs_out(v);
    	}
    }
    
    int getLCA (int a,int b)
    {
    	int k;
    	a=ID[a];
    	b=ID[b];
    	if (a>b)
    		k=a,a=b,b=k;
    	k=(int)(log(1.0+b-a)/log(2.0));
    	if (B[RMQ[a][k]] < B[RMQ[b-(1<<k)+1][k]])
    		return F[RMQ[a][k]];
    	else
    		return F[RMQ[b-(1<<k)+1][k]];
    }
    
    void Deal () //LCA在线算法   lca+rmq的过程
    {
    	int q;
    	string s1,s2;
    	scanf("%d",&q);
    	while (q--)
    	{
    		cin>>s1;
    		if (s1[0] == 'L')
    		{
    			printf("%s\n",data[0]);
    			Dfs_out (0);
    		}
    		else if (s1[0] == 'b')
    		{
    			cin>>s2;
    			printf("%d\n",Num_bro[mp[s2]]);
    		}
    		else
    		{
    			cin>>s1>>s2;
    			int u = mp[s1];
    			int v = mp[s2];
    			int k=getLCA(u,v);
    
    			if (k==u || k==v)
    				k=father[k];
    			for (int i=0; i<strlen(data[k]);i++)
    				if (data[k][i] != '.')
    					printf("%c",data[k][i]);
    			printf("\n");
    		}
    	}
    }
    
    int main ()
    {
    	while (scanf("%d",&n) && n)
    	{
    		init ();
    		Input ();
    		Cal ();
    		DFS (0,0);
    		init_RMQ();
    		Deal ();
    	}
    	return 0;
    }