L L2-4 缘之空

题目地址：

https://ac.nowcoder.com/acm/contest/5587/L

基本思路：

非常裸的lca和树上距离，由于没有给哪里是根，所以我们记录一下没有父节点就是根，然后对于每次查询的,，我们先判断是不是两个中的一个，然后再根据树上两点距离进一步判断YES or NO然后输出就行了。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define ll long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
const int maxn = 2e5 + 10;
int n,q;
struct edge {
    int next, v;
}edges[maxn*2];
int cnt;
int head[maxn];
void init() {
  memset(head, -1, sizeof(head));
  cnt = 0;
}
void add_edge(int u,int v) {
  edges[cnt].next = head[u];
  edges[cnt].v = v;
  head[u] = cnt++;
}
int dep[maxn];
int f[maxn][21];
void dfs(int u,int fa) {
  dep[u] = dep[fa] + 1;
  for (int i = 0; i <= 19; i++)
    f[u][i + 1] = f[f[u][i]][i];
  for (int i = head[u]; i != -1; i = edges[i].next) {
    int v = edges[i].v;
    if (v == fa)
      continue;
    f[v][0] = u;
    dfs(v, u);
  }
}
int lca(int x,int y) {
  if (dep[x] < dep[y])
    swap(x, y);
  for (int i = 20; i >= 0; i--) {
    if (dep[f[x][i]] >= dep[y])
      x = f[x][i];
    if (x == y)
      return x;
  }
  for (int i = 20; i >= 0; i--) {
    if (f[x][i] != f[y][i]) {
      x = f[x][i];
      y = f[y][i];
    }
  }
  return f[x][0];
}
int dist(int a,int b){
  return dep[a] + dep[b] - 2 * dep[lca(a, b)];
}
bool use[maxn];
signed main() {
  IO;
  cin >> n >> q;
  init();
  mset(use,false);
  rep(i,1,n-1){
    int u,v;
    cin >> u >> v;
    add_edge(u,v);
    add_edge(v,u);
    use[v] = true;
  }
  int root = 1;
  rep(i,1,n) if(!use[i]) root = i;
  dfs(root,0);
  while (q--){
    int a,b;
    cin >> a >> b;
    int l = lca(a,b);
    int dis = dist(a,b);
    if(l == a || l == b || dis <= 4) cout << "NO" << '\n';
    else cout << "YES" << '\n';
    cout << dis << '\n';
  }
  return 0;
}