意甲冠军：

考虑到一棵树，m询价  不要求回答每一次询价u和v通过在两个节点形成的最低等级点路径

思路：

一開始以为是LCA…  只是T了好几次…  后来发现不用LCA也可做

考虑每一个询问u和v  假设他们的lca不是1  则1一定是答案  只是求lca会T  那么我们仅仅须要在遍历树的时候给节点染色  染的颜色就是1的儿子的颜色  假设x这个点在y的子树中（y是1的儿子）那么他的颜色就是y

染完色后我们考虑答案是怎样构成的

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvaG91c2VyYWJiaXQ=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast" alt="">

如图所看到的  答案即是  红色  蓝色  绿色的子树中节点的最小值  那么我们仅仅须要分开三部分求解就可以

定义f[u][x]表示以u为根的子树中第x大的节点标号  这个能够通过树形dp求解  有了这个就能够解决绿色和红色的部分

定义g[u]表示u节点上面到1的路径中旁側的子树的最小节点标号  即图中蓝色部分  也能够利用f做树形dp求解

注意：

题目中不让蓝色部分包括绿色部分  也不把绿色部分放在红色部分中考虑的原因就是u和v节点中的一个可能是1

因为我写的是dfs  杭电会爆栈  所以记得加栈  并用C++提交

代码：

#pragma comment(linker, "/STACK:102400000,102400000")

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define N 1000010

int f[N][4], g[N], col[N], head[N];

int n, m, color, tot, ans;

struct edge {

    int v, next;

} ed[N * 2];

int d(int a, int b) {

    if (a < b)

        return a;

    return b;

}

void add(int u, int v) {

    ed[tot].v = v;

    ed[tot].next = head[u];

    head[u] = tot++;

}

void dfs1(int u, int fa) {

    int i, v;

    if (u != 1)

        col[u] = color;

    for (i = head[u]; ~i; i = ed[i].next) {

        v = ed[i].v;

        if (u == 1)

            color = v;

        if (v != fa) {

            dfs1(v, u);

            f[u][3] = d(v, f[v][0]);

            sort(f[u], f[u] + 4);

        }

    }

}

void dfs2(int u, int fa) {

    if (fa != 1) {

        if (d(u, f[u][0]) != f[fa][0])

            g[u] = f[fa][0];

        else

            g[u] = f[fa][1];

        if (g[u] > g[fa])

            g[u] = g[fa];

    }

    int i, v;

    for (i = head[u]; ~i; i = ed[i].next) {

        v = ed[i].v;

        if (v != fa)

            dfs2(v, u);

    }

}

int main() {

    int i, j, u, v;

    while (~scanf("%d%d", &n, &m)) {

        for (i = 1; i <= n; i++) {

            f[i][0] = f[i][1] = f[i][2] = f[i][3] = g[i] = N;

            head[i] = -1;

        }

        col[1] = 1;

        tot = ans = 0;

        for (i = 1; i < n; i++) {

            scanf("%d%d", &u, &v);

            add(u, v);

            add(v, u);

        }

        dfs1(1, 1);

        dfs2(1, 1);

        for (i = 1; i <= m; i++) {

            scanf("%d%d", &u, &v);

            u ^= ans;

            v ^= ans;

            if (col[u] == col[v]) {

                if (u == 1 || v == 1)

                    ans = 2;

                else

                    ans = 1;

            } else {

                if (u > v)

                    swap(u, v);

                ans = min(f[v][0], min(g[u], g[v]));

                if (u != 1) {

                    ans = min(ans, f[u][0]);

                    v = min(col[v], f[col[v]][0]);

                    u = min(col[u], f[col[u]][0]);

                    for (j = 0; j < 3; j++) {

                        if (f[1][j] != u && f[1][j] != v) {

                            ans = min(ans, f[1][j]);

                            break;

                        }

                    }

                } else {

                    v = min(col[v], f[col[v]][0]);

                    for (j = 0; j < 3; j++) {

                        if (f[1][j] != v) {

                            ans = min(ans, f[1][j]);

                            break;

                        }

                    }

                }

            }

            printf("%d\n", ans);

        }

    }

    return 0;

}