「TJOJ1109」张老师和石头的battle

题目描述

由于临近比赛，张老师和石头的题目还剩一道没出完，他们因为由谁出这最后一道，打起来了。他们找到了新格尔公司的天才程序员菜哭武，让菜哭武来决定谁来出最后一道题。于是菜哭武想到这样一个游戏，在一棵多叉树上面，让张老师和石头任意选择一个节点，每次让张老师先走，每次走到当前节点的父亲节点上，石头后走。当一个人走到了另一个人的祖先节点上，就算获胜，不用出这最后一道题。

输入

第一行，一个正整数 t（0<t<10），表示数据组数。
每组第一行包含两个数 N, M( N, M≤100,000)，N表示树的节点数，M表示询问数，节点的编号为1到 N。
接下来 N−1行，每行2个整数 A, B (1≤A, B≤N)，表示编号为 A的节点是编号为 B的节点的父亲。
接下来 M行，每行有2个数，表示 Teacher和 Stone的初始位置的编号 X, Y (1≤X, Y≤N, X≠Y)，Teacher总是先移动。

输出

对于每次数据，输出 M+1行。

第一行输出 Case #t:，t表示第 t组数据

第二到第 M+1行输出每组询问获胜者的名字（顺序与输入顺序相同）。

样例输入

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

样例输出

Case #1:
Teacher
Case #2:
Stone
Teacher

题解

太久没打题，居然在这种题上RE了无数次，太菜了。

直接求个lca，比较一下距离就行了。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (!(ch >= '0'&&ch <= '9')) { if (ch == '-')f = -1; ch = getchar(); }
    while (ch >= '0'&&ch <= '9') { x = x * 10 + (ch - '0'); ch = getchar(); }
    return x*f;
}
int n, q, cnt;
int deep[500001], head[500001], fa[500001][20];
bool vis[500001];
struct data {
    int to, next;
    void clear() { to = 0, next = 0; }
}e[1000001];
void ins(int u, int v)
{
    e[++cnt].to = v; e[cnt].next = head[u]; head[u] = cnt;
}
void insert(int u, int v)
{
    ins(u, v);
    ins(v, u);
}
void dfs(int x)
{
    vis[x] = 1;
    for (int i = 1; i <= 18; i++)
    {
        if (deep[x] < (1 << i))
            break;
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
    }
    for (int i = head[x]; i; i = e[i].next)
    {
        if (vis[e[i].to])
            continue;
        deep[e[i].to] = deep[x] + 1;
        fa[e[i].to][0] = x;
        dfs(e[i].to);
    }
}
int lca(int x, int y)
{
    if (deep[x] < deep[y])
        swap(x, y);
    int d = deep[x] - deep[y];
    for (int i = 0; i <= 18; i++)
        if ((1 << i)&d)
            x = fa[x][i];
    for (int i = 18; i >= 0; i--)
        if (fa[x][i] != fa[y][i])
        {
            x = fa[x][i];
            y = fa[y][i];
        }
    if (x == y)
        return x;
    else return fa[x][0];
}
int dis(int x, int y)
{
    int t = lca(x, y);
    return deep[x] + deep[y] - 2 * deep[t];
}
 
int main()
{
    //freopen("a.txt", "r", stdin);
    int t;
    t = read();
    for (int pp = 1; pp <= t; pp++)
    {
        memset(fa, 0, sizeof(fa));
        memset(head, 0, sizeof(head));
        memset(deep, 0, sizeof(deep));
        memset(vis, 0, sizeof(vis));
        for (int u = 0; u <= 1000000; u++)
            e[u].clear();
        n = read(); q = read();
        for (int i = 1; i < n; i++)
        {
            int u, v;
            u = read(); v = read();
            insert(u, v);
        }
        dfs(1);
        cout << "Case #" << pp << ":" << endl;
        for (int i = 1; i <= q; i++)
        {
            int x, y;
            x = read(), y = read();
            int deep_lca = lca(x, y);
 
            if (dis(x, deep_lca) <= dis(y, deep_lca))
                printf("Teacher");
            else
                printf("Stone");
            if (pp == t && i == q)
                ;
            else
                printf("\n");
        }
    }
    return 0;
}