hdu 4547(tarjan LCA)

阅读量：4936 次

发布时间：2019-06-11

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

比较简单LCA的题目了，主要就是根据题目所给出的树边建立有向的树，然后从树根开始进行LCA，要注意的是，题目中给的操作有两种，第一种是从当前点到父亲结点，第二种是从当前点到子树中的任意一个点。

CD操作

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)

Total Submission(s): 102 Accepted Submission(s): 24

Problem Description

　　在Windows下我们可以通过cmd运行DOS的部分功能，其中CD是一条很有意思的命令，通过CD操作，我们可以改变当前目录。

　　这里我们简化一下问题，假设只有一个根目录，CD操作也只有两种方式：

　　1. CD 当前目录名\...\目标目录名 (中间可以包含若干目录，保证目标目录通过绝对路径可达)

　　2. CD .. (返回当前目录的上级目录)

　　现在给出当前目录和一个目标目录，请问最少需要几次CD操作才能将当前目录变成目标目录？

Input

输入数据第一行包含一个整数T(T<=20)，表示样例个数；

每个样例首先一行是两个整数N和M(1<=N,M<=100000)，表示有N个目录和M个询问；

接下来N-1行每行两个目录名A B(目录名是只含有数字或字母，长度小于40的字符串)，表示A的父目录是B。

最后M行每行两个目录名A B，表示询问将当前目录从A变成B最少要多少次CD操作。

数据保证合法，一定存在一个根目录，每个目录都能从根目录访问到。

Output

请输出每次询问的结果，每个查询的输出占一行。

Sample Input

2 3 1 B A C A B C 3 2 B A C B A C C A

Sample Output

2 1 2

Source

Recommend

liuyiding

#include 
     
      #include 
      #include 
       
        #include 
        
         #include 
         
          using namespace std;#define N 100100// 貌似我想错了。。。map
          
            g;struct node{ int to,next;}edge[2*N];struct node1{ int to,next,w,key,key1;}edge1[2*N];int cnt1,pre1[N];int cnt,pre[N];int mark[N];int bin[N],save[N];int ans[N],d[N];int n,m;int id;void add_edge(int u,int v){ edge[cnt].to=v; edge[cnt].next=pre[u]; pre[u]=cnt++;}void add_edge1(int u,int v,int w,int key,int key1){ edge1[cnt1].to=v; edge1[cnt1].w=w; edge1[cnt1].next=pre1[u]; edge1[cnt1].key=key; edge1[cnt1].key1=key1; pre1[u]=cnt1++;}int find(int x){ if(bin[x]==x) return x; return bin[x]=find(bin[x]);}void dfs(int f,int s,int num){ bin[s]=s; mark[s]=1; save[s]=num; for(int p=pre1[s];p!=-1;p=edge1[p].next) { int v=edge1[p].to; if(mark[v]==1) { int a=find(v);// 公共祖先 int len=save[ edge1[p].key ]-save[a]; if(edge1[p].key1 != a) len++; ans[ edge1[p].w ]=len; } } for(int p=pre[s];p!=-1;p=edge[p].next) { int v=edge[p].to; if(mark[v]==1) continue; dfs(s,v,num+1); } bin[s]=f;}int main(){ string a,b; int T; scanf("%d",&T); while(T--) { memset(d,0,sizeof(d)); memset(save,0,sizeof(save)); g.clear(); id=1; cnt=0; memset(pre,-1,sizeof(pre)); cnt1=0; memset(pre1,-1,sizeof(pre1)); scanf("%d%d",&n,&m); for(int i=0;i<=n;i++) bin[i]=i; for(int i=0;i
           
            >a>>b; if(g[a]==0) g[a]=id++; if(g[b]==0) g[b]=id++; int ta,tb; ta=g[a]; tb=g[b]; d[ta]++; add_edge(tb,ta); } for(int i=0;i
            
             >a>>b; int ta,tb; ta=g[a]; tb=g[b]; add_edge1(ta,tb,i,ta,tb); add_edge1(tb,ta,i,ta,tb); } memset(ans,0,sizeof(ans)); memset(mark,0,sizeof(mark)); for(int i=1;i

转载于:https://www.cnblogs.com/chenhuan001/archive/2013/05/17/3084467.html

你可能感兴趣的文章