有些结论看上去就是对的

懵逼的 题目

传送至 Bilibili

扯淡的 题解

闲的没事干(颓到自己想干正事了)的时候逛Menci的blog(Menci他老人家的blog上不去了_(:з」∠)_所以没有链接了_(:з」∠)_行吧又上去了)看到的…

结论:

  1. 三个点之间两两求LCA, 必定有至少两对LCA相等
  2. 那么离三个点最近的那个节点就是剩下的那一对的LCA
  1. 可以感性理解一下…如果”另一个”节点$Z$不在$LCA(X, Y)$的子树中, 那么$LCA(X, Z) == LCA(Y, Z)$这可以感性理解一下吧…而这个”另一个”节点我们是可以任意选择的…也就是说三个点之间的两两LCA至少两对相等
  2. Emmmmmmmm….如果把ans设为LCA, 那么如果ans向上移动一位, 就会使两个节点分别增加1距离, 而向下移动一位, 就一定要进入一棵子树, 同样会使总距离+1

看这张图可以更清晰一些

完了, 求LCA吧

沙茶的 代码

写起来还是非常休闲…

/**************************************************************
    Problem: 1787
    User: Cansult
    Language: C++
    Result: Accepted
    Time:3360 ms
    Memory:65744 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (500000 + 5)
#define MAXL (20 + 5)
#define pii pair<int, int>
#define mkp(a, b) make_pair(a, b)
const int root = 1;
using namespace std;
struct edg
{
    int from, to, next;
}b[MAXN << 1];
int g[MAXN], cntb, n, q, d[MAXN][MAXL], lgn, deep[MAXN];
void adn(int from, int to)
{
    b[++cntb].next = g[from], b[cntb].from = from, b[cntb].to = to;
    g[from] = cntb;
}
void dfs(int dq, int de)
{
    deep[dq] = de;
    for (int i = 1; i <= lgn; i++)
        d[dq][i] = d[d[dq][i - 1]][i - 1];
    for (int i = g[dq]; i; i = b[i].next)
    {
        if (b[i].to != d[dq][0])
        {
            d[b[i].to][0] = dq;
            dfs(b[i].to, de + 1);
        }
    }
}
pii lca(int x, int y)
{
    int re = 0;
    if (deep[x] < deep[y])
        swap(x, y);
    for (int i = lgn; i >= 0; i--)
        if (deep[d[x][i]] >= deep[y])
        {
            re += deep[x] - deep[d[x][i]];
            x = d[x][i];
        }
    if (x == y)
        return mkp(x, re);
    for (int i = lgn; i >= 0; i--)
    {
        if (d[x][i] != d[y][i])
        {
            re += ((deep[x] - deep[d[x][i]]) << 1);
            x = d[x][i], y = d[y][i];
        }
    }
    return mkp(d[x][0], re + 2);
}
void solve()
{
    for (int i = 1; i <= q; i++)
    {
        int x, xx, xxx;
        scanf("%d%d%d", &x, &xx, &xxx);
        pii lcaxy = lca(x, xx), llcaxy = lca(xx, xxx), lllcaxy = lca(xxx, x);
        if (lcaxy.first == llcaxy.first)    printf("%d %d\n", lllcaxy.first, lllcaxy.second + lca(lllcaxy.first, xx).second);
        else if (llcaxy.first == lllcaxy.first) printf("%d %d\n", lcaxy.first, lcaxy.second + lca(lcaxy.first, xxx).second);
        else if (lllcaxy.first == lcaxy.first)  printf("%d %d\n", llcaxy.first, llcaxy.second + lca(llcaxy.first, x).second);
    }
}
int lg(int x)
{
    int re = 0;
    for (; (1 << re) <= x; re++)
    {}
    return re;
}
int main()
{
    scanf("%d%d", &n, &q);
    lgn = lg(n);
    for (int i = 1; i < n; i++)
    {
        int srx, sry;
        scanf("%d%d", &srx, &sry);
        adn(srx, sry);
        adn(sry, srx);
    }
    d[root][0] = root;
    dfs(root, 1);
    solve();
    return 0;
}

/*
6 4
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6
*/

By Van了的 Cansult