hdu_4547_CD操作(在线LCA)-白红宇

hdu_4547_CD操作(在线LCA)

阅读量：5291 次

发布时间：2019-06-14

本文共 1643 字，大约阅读时间需要 5 分钟。

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4547

题意：中文，不解释

题解：很裸的LCA，注意父目录打开子目录一次就够了，这里我才用倍增在线LCA+map过

1 #include
      
        2 #include
       
         3 #include
         4 #include
         
           5 #define F(i,a,b) for(int i=a;i<=b;i++) 6 #pragma comment(linker, "/STACK:1024000000,1024000000") 7 using namespace std; 8 map
          
           cnt; 9 const int N=1e5+5,DEG=18;10 int t,n,m,a,b,ed,g[N],nxt[N],v[N],w[N],fa[N][DEG],dep[N],idx;11 bool fg[N];12 string s1,s2;13 inline void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;}14 15 int Abs(int a){
    return a>0?a:-a;}16 void dfs(int u,int pre){17     dep[u]=dep[pre]+1,fa[u][0]=pre;18     F(i,1,DEG-1)fa[u][i]=fa[fa[u][i-1]][i-1];19     for(int i=g[u];~i;i=nxt[i])if(v[i]!=pre)dfs(v[i],u);20 }21 22 int LCA(int a,int b){23     if(dep[a]>dep[b])a^=b,b^=a,a^=b;24     if(dep[a]
           
            <
            
             =0;i--)26 if(fa[a][i]!=fa[b][i])a=fa[a][i],b=fa[b][i];27 return a;28 }29 30 int main(){31 scanf("%d",&t);32 while(t--){33 scanf("%d%d",&n,&m);34 cnt.clear();35 F(i,1,n)g[i]=-1,fg[i]=0;ed=0,idx=1;36 F(i,1,n-1){37 cin>>s1>>s2;38 a=cnt[s1],cnt[s1]=(a==0)?idx++:a,a=(a==0?idx-1:a);39 b=cnt[s2],cnt[s2]=(b==0)?idx++:b,b=(b==0?idx-1:b);40 adg(b,a),fg[a]=1;41 }42 int root;43 F(i,1,n)if(!fg[i]){root=i;break;}44 dep[root]=0;45 dfs(root,root);46 F(i,1,m){47 cin>>s1>>s2;48 a=cnt[s1],b=cnt[s2];49 int lca=LCA(a,b),ans=0;50 if(lca==a&&lca!=b)ans=1;51 else if(lca==b&&lca!=a)ans=Abs(dep[a]-dep[b]);52 else if(lca!=a&&lca!=b)ans=Abs(dep[a]-dep[lca])+1;53 printf("%d\n",ans);54 }55 }56 return 0;57 }