A~D水题

E宽搜，但代码很长

F题区间dp

G

预处理出一个点i子树中最小的数和从1到i的路径的外链最小的数

保存3个（自己想为啥）

染色一下求是否经过根节点

特判一下当询问中两个数有一个是1

然后就过了（但没有完全过）

看代码

#include <bits/stdc++.h>
using namespace std;
int n, q, u[2000006], v[2000005], head[2000005], net[2000005], dp[1000005], nm[1000005], ans, lans, ax, ay,
    fvv[1000005];
struct sb {
    int xx, yy;
} nm2[1000005][4];
bool cmp(sb xq, sb yq) { return xq.xx < yq.xx; }
void sb(int x, int fa)  // 3个最小
{
    nm[x] = x;
    for (int i = head[x]; i; i = net[i]) {
        if (v[i] != fa && v[i] != 0) {
            sb(v[i], x);
            if (nm[v[i]] == 0)
                continue;
            nm[x] = min(nm[x], nm[v[i]]);
            if (nm2[x][3].xx > nm[v[i]]) {
                nm2[x][3].xx = nm[v[i]];
                nm2[x][3].yy = v[i];
            }
            sort(nm2[x] + 1, nm2[x] + 1 + 3, cmp);
        }
    }
    return;
}
void dfs1(int x, int fa)  //外链最小
{
    dp[x] = dp[fa];
    for (int i = 1; i <= 3; i++) {
        if (nm2[fa][i].yy != x && fa != 1) {
            dp[x] = min(dp[x], nm2[fa][i].xx);
        }
    }
    for (int i = head[x]; i; i = net[i]) {
        if (v[i] != fa && v[i] != 0) {
            dfs1(v[i], x);
        }
    }
    return;
}
void dfs2(int x, int fa, int yan)  //染色
{
    fvv[x] = yan;
    for (int i = head[x]; i; i = net[i]) {
        if (v[i] != fa && v[i] != 0) {
            dfs2(v[i], x, yan);
        }
    }
    return;
}
int main() {
    while (~scanf("%d%d", &n, &q)) {
        ans = 1145141;
        lans = 0;
        for (int i = 1; i <= 2 * n; i++) {
            dp[i] = nm[i] = nm2[i][1].xx = nm2[i][2].xx = nm2[i][3].xx = 1145141;
            net[i] = net[i + n] = -1;
            head[i] = head[i + n] = -1;
        }
        for (int i = 1; i <= n - 1; i++) {
            scanf("%d%d", &u[i], &v[i]);
            u[i + n - 1] = v[i], v[i + n - 1] = u[i];
            net[i] = head[u[i]], head[u[i]] = i;
            net[i + n - 1] = head[v[i]], head[v[i]] = i + n - 1;
        }
        sb(1, 0);
        for (int i = head[1]; i; i = net[i]) {
            dfs1(v[i], 1);
        }
        for (int i = head[1]; i; i = net[i]) {
            dfs2(v[i], 1, v[i]);
        }
        for (int i = 1; i <= q; i++) {
            ans = 1145141;
            scanf("%d%d", &ax, &ay);
            ax = ax ^ lans, ay = ay ^ lans;
            if (fvv[ax] == fvv[ay]) {
                lans = 1;
                printf("%d\n", 1);
            } else {
                if (ax > ay)
                    swap(ax, ay);
                if (ax == 1) {
                    ans = min(nm2[ay][1].xx, dp[ay]);
                    for (int i = 1; i <= 3; i++) {
                        if (fvv[nm2[1][i].yy] != fvv[ay]) {
                            ans = min(ans, nm2[1][i].xx);
                        }
                    }
                } else {
                    ans = min(nm2[ax][1].xx, nm2[ay][1].xx);
                    ans = min(ans, min(dp[ax], dp[ay]));
                    for (int i = 1; i <= 3; i++) {
                        if (fvv[nm2[1][i].yy] != fvv[ax] && fvv[nm2[1][i].yy] != fvv[ay]) {
                            ans = min(ans, nm2[1][i].xx);
                        }
                    }
                }
                if (ans == 1145141)
                    ans = n;
                lans = min(ans, n);
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}

然后你就收获了一个MLE