来源

原题目: 杭州电子科技大学 OnlineJudge
VirtualJudge: vjudge.net

题目

坎格鲁斯普雷和袋鼠将军在游玩一款名叫“战争游戏”的游戏，在这款游戏中，坎格鲁斯普雷是进攻方，袋鼠将军是防守方。
游戏的地图可以抽象为一张有着 n 个节点的树。初始时，防守方的人物在 s 号节点。
游戏将会进行 10100 回合，在每一回合中，游戏的流程如下：
首先，进攻方会选择一个节点 p ，作为轰炸中心，并对防守方进行“轰炸预告”，如果在回合结束时防守方所在的节点 t 与轰炸中心 p 的距离不超过轰炸半径 r1 ，那么防守方的人物将会被炸死，此时游戏结束，进攻方获胜。之后 防守方可以操纵他的人物移动到与当前位置的距离不超过 r2
的节点上，然后回合结束。如果防守方的人物在回合结束时没被炸死，那么接着进行下一轮游戏，直到游戏轮次耗尽。若游戏轮次耗尽的时候防守方操纵的人物仍未死亡，那么防守方获胜，游戏结束。
作为袋鼠中的精英，坎格鲁斯普雷和袋鼠将军都是绝顶聪明的（即他们做出的操作都是当前盘面下的最优操作），那么在游戏结束时，谁将获胜？

Input

输入第一行一个整数 T，表示测试数据组数。 (1≤T≤103)
每组测试数据，第一行四个整数 n ， s ， r1 ， r2 。 (1≤n≤105,1≤s,r1,r2≤n)
之后 (n−1) 行，每行两个整数 ui ， vi ，表示一条存在于树内的边。 (1≤ui,vi≤n)
数据保证 ∑n≤2×106。

Output

对于每组测试数据，若坎格鲁斯普雷获胜，输出一行一个字符串 Kangaroo_Splay ；否则，输出一行一个字符串 General_Kangaroo 。每组测试数据的答案之间需换行。

Sample:

Input

2
5 3 2 3
1 2
2 3
3 4
3 5
5 1 1 3
1 2
2 3
3 4
3 5

Output

Kangaroo_Splay
General_Kangaroo

重点

在一棵树上 r1 * 2 < tree_distance 且 r2 >= r1 * 2 + 1 的情况下 Kangaroo 会输。

  • tree_distance 指树的直径。

代码

#include <iostream>
#include <vector>
using namespace std;

vector<vector<unsigned int>> tree;
vector<unsigned int> dis;
unsigned int dstn;
unsigned int dst;

void dfs(unsigned int u, unsigned int fa) {
    for (unsigned int v : tree[u]) {
        if (v == fa) {
            continue;
        }
        dis[v] = dis[u] + 1;
        dstn = dis[v] > dis[dstn] ? v : dstn;
        dfs(v, u);
    }
}

int main() {
    unsigned int t;
    scanf("%u", &t);
    while (t--) {
        unsigned int n, s, r1, r2;
        scanf("%u%u%u%u", &n, &s, &r1, &r2);

        dstn = 0;
        tree.clear();
        tree.resize(n + 1);
        dis.resize(n + 1);

        for (unsigned int i(1); i <= n - 1; i++) {
            unsigned int u, v;
            scanf("%u%u", &u, &v);
            tree[u].emplace_back(v);
            tree[v].emplace_back(u);
        }

        dfs(1, 0);
        dis[dstn] = 0;
        dfs(dstn, 0);
        dst = dis[dstn];

        if (r1 * 2 < dst && r2 >= r1 * 2 + 1) {
            printf("General_Kangaroo\n");
        } else {
            printf("Kangaroo_Splay\n");
        }
    }
    return 0;
}