题意：在一棵树上求距离中点，若距离是奇数则输出中间两个点。
思路：看到题意第一反应是lca，再看一下数据量那么小。。。一定有什么简单的做法。其实只要dfs一下就可以了保存路径输出中间的两个点。
代码如下：
1 /************************************************** 2 * Author : xiaohao Z 3 * Blog : http://www.cnblogs.com/shu-xiaohao/ 4 * Last modified : 2014-02-05 18:39 5 * Filename : uva_10938.cpp 6 * Description : 7 * ************************************************/ 8 9 #include <iostream> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <cmath> 14 #include <algorithm> 15 #include <queue> 16 #include <stack> 17 #include <vector> 18 #include <set> 19 #include <map> 20 #define MP(a, b) make_pair(a, b) 21 #define PB(a) push_back(a) 22 23 using namespace std; 24 typedef long long ll; 25 typedef pair<int, int> pii; 26 typedef pair<unsigned int,unsigned int> puu; 27 typedef pair<int, double> pid; 28 typedef pair<ll, int> pli; 29 typedef pair<int, ll> pil; 30 31 const int INF = 0x3f3f3f3f; 32 const double eps = 1E-6; 33 const int LEN = 10100; 34 vector<int> Map[LEN]; 35 int n, vis[LEN], path[LEN], ed; 36 37 void dfs(int v, int dep) 38 { 39 vis[v] = 1; 40 path[dep] = v; 41 if(v == ed){ 42 if(dep%2==0) printf("The fleas meet at %d. ", path[dep/2]); 43 else printf("The fleas jump forever between %d and %d. ", min(path[dep/2], path[dep/2+1]), max(path[dep/2], path[dep/2+1])); 44 } 45 for(int i=0; i<Map[v].size(); i++){ 46 if(!vis[Map[v][i]]) dfs(Map[v][i], dep+1); 47 } 48 } 49 int main() 50 { 51 // freopen("in.txt", "r", stdin); 52 53 int a, b, st; 54 while(scanf("%d", &n)!=EOF && n){ 55 for(int i=0; i<LEN; i++)Map[i].clear(); 56 for(int i=0; i<n-1; i++){ 57 scanf("%d%d", &a, &b); 58 Map[a].PB(b); 59 Map[b].PB(a); 60 } 61 int q; 62 scanf("%d", &q); 63 for(int i=0; i<q; i++){ 64 scanf("%d%d", &st, &ed); 65 memset(vis, 0, sizeof vis); 66 memset(path, 0, sizeof path); 67 dfs(st, 0); 68 } 69 } 70 return 0; 71 }