Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

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.

The input file contains multiple test cases. Each test case starts with an integer n, the number of leaves and forks in the tree, 1≤n≤5000. We assume that leaves and forks are numbered from 1 to n. Each of the following n-1 lines describe tree branches; each branch is described by two integers a and b, meaning that the branch connects the fork or leaf labeled a and the fork or leaf labeled b. In the (n+1)-st line there is one integer l, 1≤l≤500, saying how many starting positions of the fleas you are to consider for the tree. Each of the following l lines contains two positive integers (not greater than n). These numbers define the tree places in which the fleas start their jumping. Input is terminated by the case with n equal to 0.

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;
}