| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1246480 | hashdfdfh | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define int long long
const int MAXN = 2e5 + 5;
const int INF = 9e18;
int n, k;
vector<pair<int, int>> adj[MAXN]; // {to, weight}
long long deep[MAXN]; // deep[u] = sum of edge weights from root to u
int diep[MAXN]; // diep[u] = number of edges from root to u
int ans = INF;
// 普通 DFS，不进行轻重链分解
unordered_map<long long, int> dfs(int u, int parent) {
unordered_map<long long, int> local_map;
local_map[deep[u]] = diep[u]; // 初始化当前节点的信息
for (auto item : adj[u]) {
int v = item.first;
int w = item.second;
if (v == parent) continue;
// 递归处理子树
auto child_map = dfs(v, u);
// 合并子树信息到当前 local_map
for (auto item : child_map) {
int key = item.first;
int val = item.second;
if (local_map.count(key)) {
local_map[key] = min(local_map[key], val);
}
else {
local_map[key] = val;
}
}
}
// 查询是否存在满足条件的路径
// 我们需要找的是: deep[u] + deep[v] - 2*deep[lca] = k
// 这里的实现是简化版，可能需要调整
long long target = k + 2 * deep[u] - deep[u]; // 需要更精确的计算
if (local_map.count(target)) {
ans = min(ans, local_map[target] + diep[u] - 2 * diep[u]);
}
return local_map;
}
signed main() {
cin >> n >> k;
for (int i = 1; i < n; ++i) {
int u, v, w;
cin >> u >> v >> w;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
// 初始化 deep 和 diep
function<void(int, int)> init = [&](int u, int p) {
for (auto item : adj[u]) {
int v = item.first;
int w = item.second;
if (v == p) continue;
deep[v] = deep[u] + w;
diep[v] = diep[u] + 1;
init(v, u);
}
};
deep[0] = 0;
diep[0] = 0;
init(0, -1);
// 运行 DFS
dfs(0, -1);
if (ans == INF) ans = -1;
cout << ans << endl;
return 0;
}