瓜瓜去旅游

一共能走 $k$ 步，我们希望能让返程所走的次数最小，这样访问的城市会更多。

首先我们可以确定每条线路最多重复经过一次，于是我们只需要贪心地让只经过一次的线路数量最多，也就是求一条最长链，如果走完最长链还有剩下的步数，我们将剩余步数除 $2$ 产生的贡献加上即可。

树上求最长链也就是求树的直径，经典树形dp。

一次树形dp

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
int main(){
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<std::vector<int>> g(n); 
    for(int i = 1; i <= m; i++){
        int a, b;
        std::cin >> a >> b;
        a -= 1, b -= 1;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int diameter = 0;
    // 求最大直径
    std::function<int(int,int)> dfs = [&](int u, int fa){
        int mx = 0;
        for(auto v : g[u]){
            if(v == fa) continue;
            int t = dfs(v, u);
            diameter = std::max(diameter, t + mx + 1);
            mx = std::max(mx, t);
        }
        mx += 1;
        diameter = std::max(diameter, mx);
        return mx;
    };
    dfs(0, 0);
    int res = 1;
    //注意边界问题
    if(diameter > k) res = k + 1;
    else res = std::min(n, diameter + (k - diameter + 1) / 2);
    std::cout << res;
}

两次dfs求最大直径

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

int ____ = cin.tie(0)->sync_with_stdio(0);

using pii = pair<int, int>;

int main() {
  int n, m, k;
  cin >> n >> m >> k;
  vector<vector<int>> G(n + 1);
  for (int i = 1; i <= n - 1; i++) {
    int u, v;
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  
  vector<int> dep1(n + 1);
  std::function<void(int, int)> dfs1 = [&](int u, int fa) {
    dep1[u] = dep1[fa] + 1;
    for (int v : G[u]) {
      if (v != fa) {
        dfs1(v, u);
      }
    }
  };
  
  vector<int> dep2(n + 1);
  std::function<void(int, int)> dfs2 = [&](int u, int fa) {
    dep2[u] = dep2[fa] + 1;
    for (int v : G[u]) {
      if (v != fa) {
        dfs2(v, u);
      }
    }
  };

  dfs1(1, 0);
  int root = 1;
  for (int i = 1; i <= n; i++)
    if (dep1[i] > dep1[root])
      root = i;
    
  dfs2(root, 0);

  int diameter = *std::max_element(dep2.begin(), dep2.end()) - 1;

  if (k <= diameter) {
    cout << k + 1;
  } else {
    cout << std::min(diameter + 1 + (k - diameter) / 2, n);
  }

  return 0;
}