UVA10938 Flea circus(dfs)

简单题,因为是生成树,所以A到B只有唯一路径，故只要dfs,找A到B的唯一的那条路

// File Name: 10938.cpp
// Author: Zlbing
// Created Time: 2013/4/19 14:57:26

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define LL long long
#define REP(i,r,n) for(int i=r;i<=n;i++)
#define RREP(i,n,r) for(int i=n;i>=r;i--)
const int MAXN=5e3+100;
vector<int> G[MAXN];
int vis[MAXN],P[MAXN];
int dfs(int u,int s,int k)
{
    vis[u]=1;
    if(u==s){
        P[u]=k;
        return true;
    }
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(vis[v])continue;
        if(dfs(v,s,k+1)){
            //printf("u--%d v---%d\n",u,v);
            P[u]=k;
            return true;
        }
    }
    return false;
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        if(!n)break;
        REP(i,1,n)G[i].clear();
        REP(i,1,n-1)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            G[a].push_back(b);
            G[b].push_back(a);
        }
        int m;
        scanf("%d",&m);
        REP(i,1,m)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            CL(P,0);
            CL(vis,0);
            dfs(a,b,1);
            int t=P[b];
        //    printf("tttt%d\n",t);
            //REP(i,1,n)printf("P[%d]=%d\n",i,P[i]);
            if(t%2)
            {
                printf("The fleas meet at ");
                REP(i,1,n)
                    if(P[i]==(t+1)/2)
                        printf("%d.\n",i);
            }
            else{
                printf("The fleas jump forever between ");
                
                REP(i,1,n)
                    if(P[i]==t/2)a=i;
                REP(i,1,n)
                    if(P[i]-1==t/2)b=i;
                int m=min(a,b);
                int mm=max(a,b);
                printf("%d and %d.\n",m,mm);
            }
        }
    }
    return 0;
}