A

认为树以 为根。

显然，牛牛和路由器均以最优策略移动时，两者会在某个叶子处相遇，且牛牛会从 一直往下，追到这个叶子。那么我们就要求所有可能到达的叶子中最深的那个。

我们写下从 到 ，一路向上经过的节点序列。设其长度为 。那么路由器在不会被抓住的情况下，向上走最高能到达的点就是这个序列的第 个点。设它为 ，则 的子树内的所有叶子，路由器都能到达。

因此用一次 DFS 即可求出答案。

int to[200005], nxt[200005], at[100005], cnt;
int lst[100005], fa[100005], maxdep[100005];
void dfs(int cur, int f, int dep){
    fa[cur] = f;
    maxdep[cur] = dep;
    for (int i = at[cur]; i; i = nxt[i]){
        int v = to[i];
        if (v == f) continue;
        dfs(v, cur, dep + 1);
        maxdep[cur] = max(maxdep[cur], maxdep[v]);
    }
}
class Solution {
public:
    int solve(int n, int x, vector<Point>& Edge) {
        memset(at, 0, sizeof(at));
        cnt = 0;
        for (auto& p: Edge){
            to[++cnt] = p.x, nxt[cnt] = at[p.y], at[p.y] = cnt;
            to[++cnt] = p.y, nxt[cnt] = at[p.x], at[p.x] = cnt;
        }
        dfs(1, 0, 1);
        int tot = 0;
        int tmp = x;
        while (tmp != 0) 
            lst[++tot] = tmp, tmp = fa[tmp];
        return maxdep[lst[tot >> 1]];
    }
};

B

设 为处理完前 列，第 列是否交换（ 为不交换， 为交换）的情况下，使前 列合法的最少操作次数。则转移方程容易写出。

int dp[100005][2];
class Solution {
public:
    int arrange(vector<int>& f, vector<int>& s) {
        memset(dp, 0x3f, sizeof(dp));
        int n = f.size();
        dp[1][0] = 0, dp[1][1] = 1;
        for (int i = 2; i <= n; ++i){
            if (f[i - 1] < f[i - 2] && s[i - 1] > s[i - 2]){
                dp[i][0] = min(dp[i][0], dp[i - 1][0]);
            }
            if (f[i - 1] < s[i - 2] && s[i - 1] > f[i - 2]){
                dp[i][0] = min(dp[i][0], dp[i - 1][1]);
            }
            if (s[i - 1] < f[i - 2] && f[i - 1] > s[i - 2]){
                dp[i][1] = min(dp[i][1], dp[i - 1][0] + 1);
            }
            if (s[i - 1] < s[i - 2] && f[i - 1] > f[i - 2]){
                dp[i][1] = min(dp[i][1], dp[i - 1][1] + 1);
            }
        }
        int ans = min(dp[n][0], dp[n][1]);
        if (ans == 0x3f3f3f3f) return -1;
        return ans;
    }
};

C

按照给出的定义，仿照快速乘计算即可。

不过这个东西是否有结合律还有待说明，我做的时候是直接猜他有，不然快速乘是有问题的。

const int M = 1000000007;
inline int modadd(int x, int y){
    return (x + y >= M ? x + y - M: x + y);
}
int poww(int a, int b){
    int res = 1;
    while (b > 0){
        if (b & 1)
            res = 1ll * res * a % M;
        a = 1ll * a * a % M, b >>= 1;
    }
    return res;
}
inline int inv(int x){
    return poww(x, M - 2);
}
class Solution {
    Point add(Point a, Point b){
        int k;
        if (a.x == b.x && a.y == b.y){
            k = 1ll * a.x * a.x % M;
            k = 3ll * k % M;
            k = modadd(k, 1);
            k = 1ll * k * inv(2ll * a.y % M) % M;
        }else{
            k = modadd(b.y, M - a.y);
            k = 1ll * k * inv(modadd(b.x, M - a.x)) % M;
        }
        int resx = 1ll * k * k % M;
        resx = modadd(resx, M - a.x);
        resx = modadd(resx, M - b.x);
        int resy = 1ll * k * modadd(a.x, M - resx) % M;
        resy = modadd(resy, M - a.y);
        Point rres;
        rres.x = resx, rres.y = resy;
        return rres;
    }
public:
    Point NTimesPoint(Point P, int n) {
        if (n == 1) return P;
        --n;
        Point tmp = P;
        while (n > 0){
            if (n & 1) P = add(P, tmp);
            tmp = add(tmp, tmp);
            n >>= 1;
        }
        return P;
    }
};