题解：P12534 [XJTUPC 2025] 奥日

· · 题解

思路

题意是要你在树上走一条非简单路径，使得遍历到的点数量最多，且路径经过的总点数与其差值不超过 k。

假设你已经知道要遍历哪一个连通块了，你肯定也知道怎么走最优：找到直径，从它的一端开始 DFS 遍历，最后到直径另一端结束。

这样为何最优？因为如果要回到出发点 s，无论你怎么走都要走过 2x-1 个点，其中 x 为连通块大小（因为你要经过 2(x-1) 条边）。那你如果不回到出发点，而是停在 t，你就能少走 \text{dis}(s,t) 个点（\text{dis}(s,t) 是 s 到 t 路径上的边数）。按照前文所述的方案，你走过的点数是 2x-1-D（其中 D 为直径长度），自然是最少的。

注意到，题目的限制是 2x-1-D-x=x-D-1\le k，故增长直径不会影响合法性。直接取原树直径即可。剩下还可以选 k 个点，只要保证与直径连通，随便任选即可。

最后把你选出的连通块跑一遍 DFS，保证直径最后遍历，即可得到答案。

代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 5;

vector<int> T[maxn];

static inline int read(){
    int x = 0;
    char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return x;
}
int dep[maxn], fa[maxn], vis[maxn];
void diameter(int x, int f, int &p){
    dep[x] = dep[f] + 1, fa[x] = f;
    if(dep[x] > dep[p]) p = x;
    for(int i = 0; i < T[x].size(); i ++){
        int j = T[x][i];
        if(j == f) continue;
        diameter(j, x, p);
    }
}
int ans[maxn << 2], ant = 0;
bool print(int x, int f, int &rest){
    if(!vis[x]){
        if(!rest) return false;
        rest --;
    }
    ans[++ ant] = x;
    int tag = 0;
    for(int i = 0; i < T[x].size(); i ++){
        int j = T[x][i];
        if(j == f) continue;
        if(vis[j]){
            tag = j;
            continue;
        }
        bool fl = print(j, x, rest);
        if(fl) ans[++ ant] = x;
    }
    if(tag) print(tag, x, rest);
    return true;
}

int main(){
    int TT = read();
    while(TT --){
        int n = read(), k = read();
        for(int i = 1; i < n; i ++){
            int u = read(), v = read();
            T[u].push_back(v), T[v].push_back(u);
        }
        int a = 0, b = 0;
        diameter(1, 0, a), diameter(a, 0, b);
        for(int i = b; i; i = fa[i]) vis[i] = 1;
        int D = dep[b], rest = k;
        print(a, 0, rest);
        printf("%d\n", ant);
        for(int i = 1; i <= ant; i ++) printf("%d ", ans[i]);
        printf("\n");
        ant = 0;
        for(int i = 1; i <= n; i ++) T[i].clear(), vis[i] = dep[i] = fa[i] = 0;
    }
    return 0;
}

一开始看成每个点经过不超过 k 次，于是爆调 1h 树形 DP。