[UVA] 10938 - Flea circus
Problem E: Flea circus
Sometimes, if you are searching for ladybugs, all you find are tree fleas. An old tree near the anthill serves as a home of two fleas who sometimes steal honeydew from aphids living on the tree. On the old tree, branches connect the forks (spaces where two or more branches meet) and leaves where the fleas can rest. Fleas are so small that the ants cannot see them and thus fleas are safe. Because of their size, the fleas satiate their appetite pretty quickly and then have a lot of energy to jump. They decide to jump toward each other complying with the following rules:
- There is exactly one way for the fleas to go from one leaf or fork in the tree to another leaf or fork without ever turning back. Each of the fleas starts jumping along such a route to the current location of the other flea.
- The fleas can only jump from one fork or leaf of the tree to another fork or leaf if they are connected by a branch.
- If the two fleas land at the same time in the same place then they decide to sit and chat for quite a while.
- If the two fleas land at the same time in two neighboring places on the tree (forks or leaves) then they keep jumping forever.
Your program should output l lines for each test case. The i-th line for a case should look like
The fleas meet at p.
where p identifies the place where the fleas meet, or
The fleas jump forever between p and r.
where p and r are two neighboring places on the tree with p ≤ r
Sample input
8 1 2 1 3 2 4 2 5 3 6 3 7 5 8 5 5 1 7 4 1 8 4 7 7 8 0
Output for sample input
The fleas meet at 2. The fleas meet at 1. The fleas jump forever between 2 and 5. The fleas meet at 1. The fleas jump forever between 1 and 2.
Piotr Rudnicki
題目描述：
有兩隻跳蚤在樹狀圖形跳，如果他們要碰面的話，會在哪裡碰面？
會有多組兩隻跳蚤的位置，問碰面結果。
如果長度是奇數，則會在中間兩個節點互相跳來跳去，永不會碰面。
題目解法：
由於樹狀圖的兩點路徑只有一條且最短，對其中一點進行 dfs 探索，並且把路徑記錄下來，
搜索到時，則輸出路徑中間的一點或兩點。
#include <stdio.h>
#include <vector>
using namespace std;
vector<int> g[5005];
int st, ed, used[5005] = {}, found, path[5005];
void dfs(int len, int nd) {
if(used[nd] || found) return;
path[len] = nd;
if(nd == ed) {
if(len%2 == 0) {
printf("The fleas meet at %d.\n", path[len/2]);
} else {
if(path[len/2] < path[len/2+1])
printf("The fleas jump forever between %d and %d.\n", path[len/2], path[len/2+1]);
else
printf("The fleas jump forever between %d and %d.\n", path[len/2+1], path[len/2]);
}
found = 1;
return;
}
used[nd] = 1;
int i;
for(i = 0; i < g[nd].size(); i++)
dfs(len+1, g[nd][i]);
used[nd] = 0;
}
int main() {
int n, q, x, y, i;
while(scanf("%d", &n) == 1 && n) {
for(i = 1; i <= n; i++)
g[i].clear();
for(i = 1; i < n; i++) {
scanf("%d %d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
scanf("%d", &q);
while(q--) {
scanf("%d %d", &st, &ed);
if(st == ed) {
printf("The fleas meet at %d.\n", st);
continue;
}
found = 0;
dfs(0, st);
}
}
return 0;
}