题面
给定一棵 N 个节点的树,每条边带有一个权值。
求一条简单路径,路径上各条边的权值和等于K,且路径包含的边的数量最少。
输入格式
第一行两个整数 N, K。
第2~N行每行三个整数x,y,z,表示一条无向边的两个端点x,y和权值z,点的编号从0开始。
输出格式
输出一个整数,表示最少边数量。
如果不存在满足要求的路径,输出-1。
数据范围
N≤200000,K≤1000000
输入样例:
4 3
0 1 1
1 2 2
1 3 4
输出样例:
2
难度:困难
时/空限制:1s / 64MB
来源:《算法竞赛进阶指南》
题解
这题卡时间, 空间, 尽量用手写的队列
套完板子, 用桶去求解, 尺取法tle
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
typedef vector<int> VI;
const int N = 2e5 + 5, K = 1e6 + 5;
int n, k, ans = N, tx[K];
int h[N], to[N << 1], co[N << 1], ne[N << 1], tot;
int siz[N], center, mxsiz, sum;
int deep[N], q[N], qu[N], t, d[N];
void add(int u, int v, int c)
{
ne[++tot] = h[u]; h[u] = tot; co[tot] = c; to[tot] = v;
}
void dfscenter(int u, int f)
{
siz[u] = 1;
int mx = 0;
for (int i = h[u]; i; i = ne[i])
{
int& y = to[i];
if (y == f) continue;
dfscenter(y, u);
siz[u] += siz[y];
mx = max(mx, siz[y]);
}
mx = max(mx, sum - siz[u]);
if (mx < mxsiz) mxsiz = mx, center = u;
}
void dfs(int u, int f, int did)
{
deep[u] = deep[f] + 1; qu[++t] = u;
if (d[u] == k) return;
for (int i = h[u]; i; i = ne[i])
{
int& y = to[i];
if (f == y || y == did) continue;
d[y] = d[u] + co[i];
if (d[y] <= k) dfs(y, u, did);
}
}
void work(int u, int f)
{
mxsiz = N; dfscenter(u, f);
deep[center] = 0;
int tail = 0;
for (int i = h[center]; i; i = ne[i])
{
int& y = to[i];
if (y == f || co[i] > k) continue;
d[y] = co[i]; t = 0;
dfs(y, center, f);
rep (j, 1, t)
{
int& x = qu[j];
if (d[x] != k && tx[k - d[x]] == 0) continue;
ans = min(ans, deep[x] + tx[k - d[x]]);
}
rep (j, 1, t)
{
int& x = qu[j];
if (tx[d[x]] && deep[x] < tx[d[x]]) tx[d[x]] = deep[x];
else if (d[x] && !tx[d[x]]) q[++tail] = d[x], tx[d[x]] = deep[x];
}
}
rep (i, 1, tail) tx[q[i]] = 0;
for (int i = h[center], c = center; i; i = ne[i])
if (ne[h[to[i]]] && to[i] != f) sum = siz[to[i]], work(to[i], c);
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> k;
rep (i, 2, n)
{
int u, v, c; cin >> u >> v >> c;
add(u + 1, v + 1, c); add(v + 1, u + 1, c);
}
sum = n; work(1, 0);
cout << (ans == N ? -1 : ans);
return 0;
}