C++题解：DTOI-5 3-1 神树

题目分析

这道题要求我们在树上找到恰好经过 k 个点的最短路径，并且可以从任意节点瞬间返回根节点。

思路分析

预处理距离： 首先，我们需要预处理出每个节点到根节点的距离。可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来完成。
贪心策略： 为了最小化总时间，我们可以使用贪心策略： - 从根节点出发。 - 每次选择距离根节点最近的未访问节点进行访问。 - 利用特殊边快速返回根节点。
优先队列优化： 为了高效地找到距离根节点最近的未访问节点，我们可以使用优先队列（例如 C++ 中的 priority_queue）来维护所有可访问节点及其距离。

代码实现cpp#include #include #include

using namespace std;

const int MAXN = 1e5 + 5;

vector adj[MAXN]; // 邻接表存储树int dist[MAXN]; // 存储每个节点到根节点的距离

void dfs(int u, int fa) { for (int v : adj[u]) { if (v == fa) continue; dist[v] = dist[u] + 1; dfs(v, u); }}

int main() { int n; cin >> n;

for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); }

// 预处理距离 dfs(1, 0);

for (int k = 1; k <= n; ++k) { long long ans = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; vector visited(n + 1, false);

pq.push({dist[1], 1}); // 从根节点开始

for (int i = 0; i < k; ++i) {      int d = pq.top().first, u = pq.top().second;      pq.pop();

  if (visited[u]) continue;      visited[u] = true;

  ans += d;

  for (int v : adj[u]) {        if (!visited[v]) {          pq.push({dist[v], v});        }      }    }

cout << ans << endl;  }

return 0;}

复杂度分析

预处理距离的时间复杂度为 O(N)，其中 N 是节点数。- 对于每个 k，优先队列的操作时间复杂度为 O(k log k)。- 因此，总时间复杂度为 O(N + N log N)，其中 N 是节点数。