link-cut-tree 被卡了，求放宽时限吧

#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>

using namespace std;

#define LOCAL 0
#define MAXN 500000
#define MAXM 500000

struct TreeNode {
  bool rev;
  uint32_t pa;
  uint32_t lc;
  uint32_t rc;
};

TreeNode tree[MAXN+1];
uint32_t ancestors[MAXN+1];

inline bool IsRoot(uint32_t p)
{
  return (tree[tree[p].pa].lc != p) && (tree[tree[p].pa].rc != p);
}

void PushDownRev(uint32_t p)
{
  if (tree[p].lc != 0) {
    tree[tree[p].lc].rev = !tree[tree[p].lc].rev;
  }
  if (tree[p].rc != 0) {
    tree[tree[p].rc].rev = !tree[tree[p].rc].rev;
  }
  swap(tree[p].lc, tree[p].rc);
  tree[p].rev = false;
}

void PushAllRev(uint32_t p)
{
  int top = 0;
  ++top;
  ancestors[top] = p;
  while (!IsRoot(p)) {
    p = tree[p].pa;
    ++top;
    ancestors[top] = p;
  }
  while (top != 0) {
    p = ancestors[top];
    --top;
    if (tree[p].rev) {
      PushDownRev(p);
    }
  }
}

void LeftRotate(uint32_t p)
{
  uint32_t q;
  q = tree[p].rc;
  tree[p].rc = tree[q].lc;
  if (tree[q].lc != 0) {
    tree[tree[q].lc].pa = p;
  }
  tree[q].pa = tree[p].pa;
  if (!IsRoot(p)) {
    if (tree[tree[p].pa].lc == p) {
      tree[tree[p].pa].lc = q;
    } else {
      tree[tree[p].pa].rc = q;
    }
  }
  tree[q].lc = p;
  tree[p].pa = q;
}

void RightRotate(uint32_t p)
{
  uint32_t q;
  q = tree[p].lc;
  tree[p].lc = tree[q].rc;
  if (tree[q].rc != 0) {
    tree[tree[q].rc].pa = p;
  }
  tree[q].pa = tree[p].pa;
  if (!IsRoot(p)) {
    if (tree[tree[p].pa].lc == p) {
      tree[tree[p].pa].lc = q;
    } else {
      tree[tree[p].pa].rc = q;
    }
  }
  tree[q].rc = p;
  tree[p].pa = q;
}

void LctSplay(uint32_t p)
{
  uint32_t f, g;
  PushAllRev(p);
  while (!IsRoot(p)) {
    f = tree[p].pa;
    g = tree[f].pa;
    if (IsRoot(f)) {
      if (p == tree[f].lc) {
        RightRotate(f);
      } else {
        LeftRotate(f);
      }
    } else if (p == tree[f].lc && f == tree[g].lc) {
      RightRotate(g);
      RightRotate(f);
    } else if (p == tree[f].rc && f == tree[g].rc) {
      LeftRotate(g);
      LeftRotate(f);
    } else if (p == tree[f].lc && f == tree[g].rc) {
      RightRotate(f);
      LeftRotate(g);
    } else {
      LeftRotate(g);
      RightRotate(f);
    }
  }
}

uint32_t LctAccess(uint32_t p) 
{
  uint32_t last = 0;
  while (p != 0) {
    LctSplay(p);
    tree[p].rc = last;
    last = p;
    p = tree[p].pa;
  }
  return last;
}

void LctMakeRoot(uint32_t p)
{
  LctAccess(p);
  LctSplay(p);
  tree[p].rev = !tree[p].rev;
}

int ReadInteger(void)
{
  int x = 0, sign = 1;
  int ch;
  ch = getchar();
  while (ch<'0' || ch>'9') {
    if (ch == '-') {
      sign = -1;
    }
    ch = getchar();
  }
  while (ch>='0' && ch<='9') {
    x = x*10 + ch-'0';
    ch = getchar();
  }
  return x*sign;
}

int main(void)
{
#if LOCAL
  freopen("test.in", "r", stdin);
  freopen("test.out", "w", stdout);
#endif
  int n, m, root;
  int u, v, lca;
  n = ReadInteger();
  m = ReadInteger();
  root = ReadInteger();
  memset(tree, 0, (n+1)*sizeof(tree[0]));
  for (int i=0; i<n-1; ++i) {
    u = ReadInteger();
    v = ReadInteger();
    LctMakeRoot(u);
    tree[u].pa = v;
  }
  LctMakeRoot(root);
  for (int i=0; i<m; ++i) {
    u = ReadInteger();
    v = ReadInteger();
    LctAccess(u);
    lca = LctAccess(v);
    printf("%d\n", lca);
  }
  return 0;
}