首页 > 代码库 > hdu 4409 Family Name List(LCA&有坑点)
hdu 4409 Family Name List(LCA&有坑点)
Family Name List
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 882 Accepted Submission(s): 271
Problem Description
Kong belongs to a huge family. Recently he got a family name list which lists all men (no women) in his family over many generations.
The list shows that the whole family has a common ancestor, let‘s call him Mr. X. Of course, everybody except Mr.X in the list is Mr. X‘s descendant. Everybody‘s father is shown in the list except that Mr. X‘s father is not recorded. We define that Mr. X‘s generation number is 0. His son‘s generation number is 1.His grandson‘s generation number is 2, and so on. In a word, everybody‘s generation number is 1 smaller than his son‘s generation number. Everybody‘s generation number is marked in some way in the list.
Now Kong is willing to pay a lot of money for a program which can re-arrange the list as he requires ,and answer his questions such as how many brothers does a certain man have, etc. Please write this program for him.
The list shows that the whole family has a common ancestor, let‘s call him Mr. X. Of course, everybody except Mr.X in the list is Mr. X‘s descendant. Everybody‘s father is shown in the list except that Mr. X‘s father is not recorded. We define that Mr. X‘s generation number is 0. His son‘s generation number is 1.His grandson‘s generation number is 2, and so on. In a word, everybody‘s generation number is 1 smaller than his son‘s generation number. Everybody‘s generation number is marked in some way in the list.
Now Kong is willing to pay a lot of money for a program which can re-arrange the list as he requires ,and answer his questions such as how many brothers does a certain man have, etc. Please write this program for him.
Input
There are no more than 15 test cases.
For each test case:
The first line is an integer N( 1 <= N <= 30,000), indicating the number of names in the list.
The second line is the name of Mr. X.
In the next N-1 lines, there is a man‘s name in each line. And if the man‘s generation number is K, there are K dots( ‘.‘) before his name.
Please note that :
1) A name consists of only letters or digits( ‘0‘-‘9‘).
2) All names are unique.
3) Every line‘s length is no more than 60 characters.
4) In the list, a man M‘s father is the closest one above M whose generation number is 1 less than M.
5) For any 2 adjacent lines in the list, if the above line‘s generation number is G1 and the lower line‘ s generation number is G2, than G2 <= G1 +1 is guaranteed.
After the name list, a line containing an integer Q(1<=Q<=30,000) follows, meaning that there are Q queries or operations below.
In the Next Q lines, each line indicates a query or operation. It can be in the following 3 formats:
1) L
Print the family list in the same format as the input, but in a sorted way. The sorted way means that: if A and B are brothers(cousins don’t count), and A‘s name is alphabetically smaller than B‘s name, then A must appear earlier than B.
2) b name
Print out how many brothers does "name" have, including "name" himself.
3) c name1 name2
Print out the closest common ancestor of "name1" and "name2". "Closest" means the generation number is the largest. Since Mr. X has no ancestor in the list, so it‘s guaranteed that there is no question asking about Mr. X‘s ancestor.
The input ends with N = 0.
For each test case:
The first line is an integer N( 1 <= N <= 30,000), indicating the number of names in the list.
The second line is the name of Mr. X.
In the next N-1 lines, there is a man‘s name in each line. And if the man‘s generation number is K, there are K dots( ‘.‘) before his name.
Please note that :
1) A name consists of only letters or digits( ‘0‘-‘9‘).
2) All names are unique.
3) Every line‘s length is no more than 60 characters.
4) In the list, a man M‘s father is the closest one above M whose generation number is 1 less than M.
5) For any 2 adjacent lines in the list, if the above line‘s generation number is G1 and the lower line‘ s generation number is G2, than G2 <= G1 +1 is guaranteed.
After the name list, a line containing an integer Q(1<=Q<=30,000) follows, meaning that there are Q queries or operations below.
In the Next Q lines, each line indicates a query or operation. It can be in the following 3 formats:
1) L
Print the family list in the same format as the input, but in a sorted way. The sorted way means that: if A and B are brothers(cousins don’t count), and A‘s name is alphabetically smaller than B‘s name, then A must appear earlier than B.
2) b name
Print out how many brothers does "name" have, including "name" himself.
3) c name1 name2
Print out the closest common ancestor of "name1" and "name2". "Closest" means the generation number is the largest. Since Mr. X has no ancestor in the list, so it‘s guaranteed that there is no question asking about Mr. X‘s ancestor.
The input ends with N = 0.
Output
Already mentioned in the input.
Sample Input
9 Kongs .son1 ..son1son2 ..son1son1 ...sonkson2son1 ...son1son2son2 ..son1son3 ...son1son3son1 .son0 7 L b son1son3son1 b son1son2 b sonkson2son1 b son1 c sonkson2son1 son1son2son2 c son1son3son1 son1son2 0
Sample Output
Kongs .son0 .son1 ..son1son1 ...son1son2son2 ...sonkson2son1 ..son1son2 ..son1son3 ...son1son3son1 1 3 2 2 son1son1 son1
Source
2012 ACM/ICPC Asia Regional Jinhua Online
Recommend
zhoujiaqi2010 | We have carefully selected several similar problems for you: 5053 5052 5051 5050 5049
题意：
给你一棵树。有三种操作。
1.输出树的dfs序。字典序小的先输出。
2.输出一个结点的父亲有多少儿子。包括自己。
3.输出u，v的LCA。
思路：
这题输入比较蛋疼。我是用一个栈来建树的。不知道有其它什么高级方法没。然后对于操作1.由于要字典序小的的先dfs。那么只好用 不是很熟悉的vector存边了。然后对边按名字字典序排序。然后dfs一次把答案存起来。对于2记录下一个结点的父亲是谁就行了。对于3.tarjan离线处理。这题有个坑点就是LCA不能是自己。over。
详细见代码：
#include<cstdio>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
#include<iostream>
#include<map>
using namespace std;
const int maxn=30010;
int cnt,ptr,pp,vis[maxn],ty[maxn],aans[maxn];
int st[maxn],rk[maxn],fa[maxn],pa[maxn],uu[maxn],vv[maxn];
char na[100];
vector<int> G[maxn];
string name[maxn],ans[maxn];
map<string,int> mp;
struct node
{
int v,id;
node *next;
} ed[maxn<<1],*head[maxn];
void adde(int u,int v,int id)
{
ed[ptr].v=v;
ed[ptr].id=id;
ed[ptr].next=head[u];
head[u]=&ed[ptr++];
}
bool cmp(int a,int b)
{
return name[a]<name[b];
}
void dfs(int u)
{
string op=".";
ans[pp]="";
for(int i=0;i<rk[u];i++)
ans[pp]+=op;
ans[pp++]+=name[u];
for(int i=0;i<G[u].size();i++)
{
pa[G[u][i]]=u;
dfs(G[u][i]);
}
}
int getfa(int x)
{
if(fa[x]==x)
return x;
return fa[x]=getfa(fa[x]);
}
void tarjan(int u)
{
vis[u]=1,fa[u]=u;
for(node *p=head[u];p!=NULL;p=p->next)
{
if(vis[p->v])
aans[p->id]=getfa(p->v);
}
for(int i=0;i<G[u].size();i++)
{
tarjan(G[u][i]);
fa[G[u][i]]=u;
}
}
int main()
{
int i,j,n,m,tp,ct,id,u,v;
string aa,bb;
char cmd[20];
while(scanf("%d",&n),n)
{
for(i=0;i<=n;i++)
G[i].clear();
mp.clear();
tp=cnt=1;
st[0]=0,rk[0]=-1;
for(i=0;i<n;i++)
{
scanf("%s",na);
ct=0;
for(j=0;na[j];j++)
if(na[j]=='.')
ct++;
else
break;
string nna(na+ct);
//cout<<nna<<endl;
if(!mp.count(nna))
{
name[cnt]=nna;
rk[cnt]=ct;
mp[nna]=cnt++;
}
id=mp[nna];
while(rk[st[tp-1]]>=rk[id])
tp--;
G[st[tp-1]].push_back(id);
st[tp++]=id;
}
for(i=1;i<=n;i++)
sort(G[i].begin(),G[i].end(),cmp);
pp=0;
dfs(1);
ptr=0;
memset(head,0,sizeof head);
memset(vis,0,sizeof vis);
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%s",cmd);
if(cmd[0]=='L')
ty[i]=0;
else if(cmd[0]=='b')
{
ty[i]=1;
cin>>aa;
id=mp[aa];
aans[i]=G[pa[id]].size();
}
else
{
ty[i]=2;
cin>>aa>>bb;
u=mp[aa],v=mp[bb];
uu[i]=u,vv[i]=v;
adde(u,v,i);
adde(v,u,i);
}
}
tarjan(1);
for(i=0;i<m;i++)
{
if(ty[i]==0)
{
for(j=0;j<n;j++)
cout<<ans[j]<<endl;
}
else if(ty[i]==1)
printf("%d\n",aans[i]);
else
{
if(aans[i]==uu[i]||aans[i]==vv[i])
aans[i]=pa[aans[i]];
cout<<name[aans[i]]<<endl;
}
}
}
return 0;
}
hdu 4409 Family Name List(LCA&有坑点)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。