hdu 4547(tarjan LCA)

比较简单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

2013金山西山居创意游戏程序挑战赛——初赛（1）

Recommend

liuyiding

#include <stdio.h>
#include <map>
#include <string.h>
#include <string>
#include <iostream>
using namespace std;
#define N 100100

// 貌似我想错了。。。

map<string,int> 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<n-1;i++)
        {
            cin>>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<m;i++)
        {
            cin>>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<id;i++)
            if(d[i]==0) 
            {
                dfs(i,i,0);
                break;
            }
        for(int i=0;i<m;i++)
            printf("%d\n",ans[i]);
    }
    return 0;
}