学步园

http://acm.hdu.edu.cn/showproblem.php?pid=4547

题意：就是给你一棵树，从一个节点到它的子孙节点只需要一步，到他的祖先节点则要一步一步地向上爬x步（x为它到其祖先节点之间的边数）。给你两个节点a,b，问从a到b最少经过多少步。

思路：额。。。就是裸的LCA，求出两个点的的LCA，设为C点，那就从a到c然后再到b，从a到c就是a和c之间的深度只差，从c到b则需要1步或0步（看c是否等于b）。然后就没有然后了。这里的LCA用树链剖分实现，节点的标号用map存储。

代码如下：

#pragma comment(linker,"/STACK:100000000,100000000")
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <algorithm>
#define maxn 100010
using namespace std;
struct edge
{
    int to;
    int next;
}e[maxn<<1];
int box[maxn],cnt,tot;
int siz[maxn],top[maxn],son[maxn],dep[maxn],fa[maxn];
void init()
{
    tot=0;
    son[0]=dep[0]=0;
    memset(box,-1,sizeof(box));
    cnt=0;
}
void add(int from,int to)
{
    e[cnt].to=to;
    e[cnt].next=box[from];
    box[from]=cnt++;
}
void dfs(int now,int pre)
{
    siz[now]=1;
    fa[now]=pre;
    son[now]=0;
    dep[now]=dep[pre]+1;
    int t,v;
    for(t=box[now];t+1;t=e[t].next)
    {
        v=e[t].to;
        if(v!=pre)
        {
            dfs(v,now);
            siz[now]+=siz[v];
            if(siz[son[now]]<siz[v])
            {
                son[now]=v;
            }
        }
    }
}
void dfs2(int now,int tp)
{
    top[now]=tp;
    if(son[now])
    dfs2(son[now],top[now]);
    int t,v;
    for(t=box[now];t+1;t=e[t].next)
    {
        v=e[t].to;
        if(v!=fa[now]&&v!=son[now])
        dfs2(v,v);
    }
}
int LCA(int a, int b)
{
    while (1)
    {
        if (top[a] == top[b])
        return dep[a] <= dep[b] ? a : b;
        else if (dep[top[a]] >= dep[top[b]])
        a = fa[top[a]];
        else b = fa[top[b]];
    }
}
struct node
{
    char str[50];
    bool operator <(const node &a)const
    {
        if(strcmp(str,a.str)<0)
        return true;
        return false;
    }
};
int vis[maxn];
map <node,int> mp;
map <node,int>::iterator itor;
int main()
{
    //freopen("dd.txt","r",stdin);
    int ncase;
    scanf("%d",&ncase);
    while(ncase--)
    {
        int n,m,num=0,i;
        scanf("%d%d",&n,&m);
        init();
        node t1,t2;
        memset(vis,0,sizeof(vis));
        mp.clear();
        for(i=1;i<n;i++)
        {
            int a,b;
            scanf("%s%s",t1.str,t2.str);
            itor=mp.find(t1);
            if(itor==mp.end())
            {
                mp.insert(make_pair(t1,++num));
                a=num;
            }
            else
            a=itor->second;
            itor=mp.find(t2);
            if(itor==mp.end())
            {
                mp.insert(make_pair(t2,++num));
                b=num;
            }
            else
            {
                b=itor->second;
            }
            vis[a]=1;
            add(b,a);
            add(a,b);
        }
        int root=0;
        for(i=1;i<=n;i++)
        {
            if(!vis[i])
            break;
        }
        root=i;
        dfs(root,0);
        dfs2(root,root);
        while(m--)
        {
            int a,b;
            scanf("%s%s",t1.str,t2.str);
            if(n==1)
            {
                printf("0\n");
                continue;
            }
            itor=mp.find(t1);
            a=itor->second;
            itor=mp.find(t2);
            b=itor->second;
            int c=LCA(a,b);
            printf("%d\n",dep[a]-dep[c]+(c==b?0:1));
        }
    }
    return 0;
}