首页 > 代码库 > HDU 4409 Family Name List --乱搞、LCA
HDU 4409 Family Name List --乱搞、LCA
题意： 给出一些名字，名字间有父子关系，有三种操作：
1.按祖先到后代，兄弟间按字典序由小到大排序，然后输出
2.求某个节点的兄弟节点有多少个，包括自己（注意，根节点的兄弟节点是1）
3.求节点a和b的公共祖先 （注意：如果公共祖先是a或b，必须要输出其父亲，与传统的LCA可以是自己不同）
解法： 先把整棵树整理出来，son[u]表示u的儿子个数，用来求兄弟个数， fa[u]表示父亲，Gson存储儿子的标号，关于排序的问题，先读入所有名字，然后排个序哈希一下，使字典序小的节点标号一定小，那么直接sort(Gson.begin(),Gson.end()) 就将儿子排序了。
然后用RMQ 搞在线LCA 即可
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <string>#include <vector>#include <map>using namespace std;#define N 30107map<string,int> mp;int son[N],fa[N],cnt[N];vector<int> Gson[N];string TS[N],NS[N];int ati[60004],f[60006],bn,b[90008],dp[60005][32],ind;void dfs(int u,int dep){ for(int i=0;i<dep;i++) printf("."); cout<<NS[u]<<endl; for(int i=0;i<Gson[u].size();i++) { int v = Gson[u][i]; dfs(v,dep+1); }}void init(){ memset(ati,0,sizeof(ati)); memset(f,0,sizeof(f)); memset(b,0,sizeof(b)); memset(dp,0,sizeof(dp)); bn = ind = 0;}void dfs_2(int u,int father){ int tmp = ++ind; f[tmp] = u; b[++bn] = tmp; ati[u] = bn; for(int i=0;i<Gson[u].size();i++) { int v = Gson[u][i]; if(v==father) continue; dfs_2(v,u); b[++bn]=tmp; }}void RMQ_init(int n){ for (int i=1; i<=n; i++) dp[i][0]=b[i]; int m=floor(log((double)n*1.0)/log((double)2.0)); for (int j=1; j<=m; j++) for (int i=1; i<=n-(1<<j)+1; i++) dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);}int RMQ(int l,int r){ int k=floor(log((double)r-l+1)/log(2.0)); return min(dp[l][k],dp[r-(1<<k)+1][k]);}int LCA(int a,int b){ if (ati[a] > ati[b]) swap(a,b); return f[RMQ(ati[a],ati[b])];}int main(){ int n,m,i,j; while(scanf("%d",&n)!=EOF && n) { mp.clear(); memset(son,0,sizeof(son)); memset(fa,0,sizeof(fa)); string ss; for(i=0;i<=n;i++) Gson[i].clear(); for(i=1;i<=n;i++) { cin>>TS[i]; int len = TS[i].length(); for(j=0;j<len;j++) if(TS[i][j] != ‘.‘) break; NS[i] = TS[i].substr(j,len-j); } sort(NS+1,NS+n+1); for(i=1;i<=n;i++) mp[NS[i]] = i; for(i=1;i<=n;i++) { ss = TS[i]; int len = ss.length(); for(j=0;j<len;j++) if(ss[j] != ‘.‘) break; string S = ss.substr(j,len-j); cnt[j] = mp[S]; if(j != 0) { fa[mp[S]] = cnt[j-1]; //最近的有j-1个‘.‘的名字就是有j个‘.‘的名字的父亲 son[cnt[j-1]]++; Gson[cnt[j-1]].push_back(mp[S]); } else fa[mp[S]] = 0; } for(i=1;i<=n;i++) sort(Gson[i].begin(),Gson[i].end()); for(i=1;i<=n;i++) if(fa[i] == 0) break; int father = i; init(); dfs_2(father,0); RMQ_init(bn); scanf("%d",&m); char s[5]; while(m--) { scanf("%s",s); if(s[0] == ‘L‘) dfs(father,0); else if(s[0] == ‘b‘) { cin>>ss; int k = mp[ss]; if(k == father) puts("1"); else printf("%d\n",son[fa[k]]); } else { string S1,S2; cin>>S1>>S2; int ms1 = mp[S1]; int ms2 = mp[S2]; int fat = LCA(ms1,ms2); if(fat == ms1 || fat == ms2) cout<<NS[fa[fat]]<<endl; else cout<<NS[fat]<<endl; } } } return 0;}
HDU 4409 Family Name List --乱搞、LCA
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。