A.小红的图

模拟即可

void solve(){
    int x,y;
    cin >> x >> y;
    cout << (x == 1 ? "L" : "R");
    cout << (y == 1 ? "U" : "D");
}

B.小红的菊花

其实不需要建树，只需给每个点计算度即可，找度最多的点就是菊花中心。

void solve(){
    int n;
    cin >> n;
    vector<int> deg(n+1);
    for (int i = 0;i < n-1;i ++){
        int x,y;
        cin >> x >> y;
        deg[x] ++;
        deg[y] ++;
    }
    cout << max_element(deg.begin(),deg.end()) - deg.begin() << "\n";
}

C.小红的好矩形

假设确定了形状和确定了一个点，那么剩下三个点的位置也是确定的，那么只需分别计算 和 的情况即可。

using i64 = long long;
void solve(){
    int x,y;
    cin >> x >> y;
    i64 ans = 0;
    ans += i64(x-1) * y;
    ans += i64(y-1) * x;
    cout << ans << "\n";
}

D.小红嫁接

因为链的每个点的度至多为 ，所以每次可以把大于 的一条边嫁接到度为 的点上。

实际实现上，我们只需贪心累计度大于 的点，结果一定是对的。

时间复杂度为 。

void solve(){
    int n;
    cin >> n;
    vector<int> deg(n+1);
    for (int i = 1;i < n;i ++){
        int x,y;
        cin >> x >> y;
        deg[x] ++;
        deg[y] ++;
    }
    int ans = 0;
    for (int i = 1;i <= n;i ++){
        if (deg[i] >= 2) ans += deg[i] - 2;
    }
    cout << ans << "\n";
}

E.小红玩马

由于我们可以反复横跳消耗步数，所以我们考虑分奇偶步数讨论。

只需 bfs 求出到达对应坐标所需的最小步数后反复横跳即可，记得特判起点和终点一样的情况，此时你需要找一个点外跳再回来。

时间复杂度为

int nxt[][2] = {
    {1,2},{1,-2},{-1,2},{-1,-2},
    {2,1},{2,-1},{-2,1},{-2,-1},
};
 
void solve(){
    int n,m,k;
    cin >> n >> m >> k;
    int x1,y1,x2,y2;
    cin >> x1 >> y1 >> x2 >> y2;
    vector<vector<vector<array<int,3>>>> dist(n+2,vector<vector<array<int,3>>>(m+2,vector<array<int,3>>(2,{k+1,0,0})));
    queue<array<int,3>> q;
    q.push({x1,y1,0});
    dist[x1][y1][0] = {0,-1,-1};
    while(q.size()){
        auto [x,y,step] = q.front();
        q.pop();
        for (int i = 0;i < 8;i ++){
            int nx = x + nxt[i][0],ny = y + nxt[i][1];
            int s = !(step&1);
            if (nx <= 0 || nx > n || ny <= 0 || ny > m) continue;
            if (dist[nx][ny][s][0] <= step + 1) continue;
            dist[nx][ny][s] = {step + 1,x,y};
            q.push({nx,ny,step+1});
        }
    }
    if (dist[x2][y2][k&1][0] > k){
        cout << "No\n";
        return;
    }
    vector<p32> ans;
    for (int cx = x2,cy = y2,s = k&1;cx != x1 || cy != y1;){
        ans.push_back({cx,cy});
        auto [st,nx,ny] = dist[cx][cy][s];
        cx = nx,cy = ny;
        s = !s;
    }
    if (ans.size() == 0){ // 特判起点等于终点的情况
        for (int i = 0;i < 8;i ++){
            int nx = x1 + nxt[i][0],ny = y1 + nxt[i][1];
            int s = 1;
            if (nx <= 0 || nx > n || ny <= 0 || ny > m) continue;
            ans.push_back({x1,y1});
            ans.push_back({nx,ny});
            break;
        }
        if (ans.size() == 0) {
            cout << "No\n";
            return;
        }
    }
    while (ans.size() < k){
        ans.push_back({x1,y1});
        ans.push_back(ans[ans.size()-2]);
    }
    reverse(ans.begin(),ans.end());
    cout << "Yes\n";
    for (auto [x,y] : ans) cout << x << " " << y << "\n";
}

F.小红的⑨

换根 dp 模板题，记录对应距离的点数量即可。

时间复杂度为 。

void solve(){
    int n;
    cin >> n;
    vector<vector<int>> G(n+1);
    for (int i = 1;i < n;i ++){
        int u,v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    vector<int> ans(n+1);
    vector<vector<int>> dist(n+1,vector<int>(10));
    auto dfs = [&](auto&& self,int u,int fa)->void{
        dist[u][0] = 1;
        for (int v : G[u]){
            if (v == fa) continue;
            self(self,v,u);
            for (int d = 0;d < 9;d ++){
                dist[u][d+1] += dist[v][d];
            }
        }
    };
    dfs(dfs,1,1);
    auto dfs2 = [&](auto&& self,int u,int fa)->void{
        ans[u] = dist[u][9];
        for (int v : G[u]){
            if (v == fa) continue;
            for (int d = 8;d >= 1;d --){
                dist[v][d+1] += dist[u][d] - dist[v][d-1];
            }
            dist[v][1] += dist[u][0];
            self(self,v,u);
        }
    };
    dfs2(dfs2,1,0);
    for (int i = 1;i <= n;i ++) cout << ans[i] << " \n"[i==n];
}