URAL 1752 Tree 2 树上最长路，rmq

对于rmq没有明确的限定边界部分，待解决

#pragma comment(linker, "/STACK:102400000000,102400000000")#include <cstdio>#include <ctime>#include <cstdlib>#include <cstring>#include <queue>#include <string>#include <set>#include <stack>#include <map>#include <cmath>#include <vector>#include <iostream>#include <algorithm>#include <bitset>using namespace std;//LOOP#define FF(i, a, b) for(int i = (a); i < (b); ++i)#define FD(i, b, a) for(int i = (b) - 1; i >= (a); --i)#define FE(i, a, b) for(int i = (a); i <= (b); ++i)#define FED(i, b, a) for(int i = (b); i>= (a); --i)#define REP(i, N) for(int i = 0; i < (N); ++i)#define CLR(A,value) memset(A,value,sizeof(A))#define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)//OTHER#define SZ(V) (int)V.size()#define PB push_back//INPUT#define RI(n) scanf("%d", &n)#define RII(n, m) scanf("%d%d", &n, &m)#define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)#define RIV(n, m, k, p) scanf("%d%d%d%d", &n, &m, &k, &p)#define RV(n, m, k, p, q) scanf("%d%d%d%d%d", &n, &m, &k, &p, &q)#define RS(s) scanf("%s", s)//OUTPUT#define WI(n) printf("%d\n", n)#define WS(n) printf("%s\n", n)typedef long long LL;typedef unsigned long long ULL;typedef vector <int> VI;const int INF = 1000000000;const double eps = 1e-10;const int MAXN = 21000;const int MOD = 1000000;vector<int>adj[MAXN];int fa[2][MAXN][20];int val[MAXN], dis[MAXN];int q[MAXN];int n, Q;int bfs(int s, int k){    CLR(dis, -1);    int head = 0, tail = 0;    dis[s] = 0; q[tail++] = s;    while (head < tail)    {        int u = q[head++];        int un = adj[u].size();        REP(r, un)        {            int v = adj[u][r];            if (dis[v] == -1)            {                dis[v] = dis[u] + 1; q[tail++] = v; fa[k][v][0] = u;            }        }    }    int p = 0, id = s;    FE(i, 1, n)    {        if (dis[i] > p)            p = dis[i], id = i;        val[i] = max(dis[i], val[i]);    }    return id;}void init(){    CLR(fa, -1);///    CLR(val, 0);///    int d1, d2;    d1 = bfs(1, 0);    d2 = bfs(d1, 0);    bfs(d2, 1);    fa[0][d1][0] = d1;///没有这两个也是对的，为何？    fa[1][d2][0] = d2;///    ///rmq初始化？    REP(k, 2)    for (int j = 1; j < 20; j++)        for (int i = 1; i <= n; i++)            if (fa[k][i][j - 1] != -1)///没有这个也是对的，为什么？            fa[k][i][j] = fa[k][fa[k][i][j - 1]][j - 1];}int jump(int u, int d, int k){    ///若d = 0，即为u    int r = 19;    while (d)    {        while ((1 << r) > d)            r--;        u = fa[k][u][r];        d -= (1 << r);    }    return u;}int main(){    int x, y;    while (~RII(n, Q))    {        REP(i, n + 1) adj[i].clear();        REP(i, n - 1)        {            RII(x, y);            adj[x].push_back(y);            adj[y].push_back(x);        }        init();        while (Q--)        {            RII(x, y);            if (val[x] < y) printf("0\n");            else if (dis[x] == val[x]) printf("%d\n", jump(x, y, 1));            else printf("%d\n", jump(x, y, 0));        }    }}