【题目描述】
给一棵树,每条边有权.求一条简单路径,权值和等于(k),且边的数量最小。
【输入格式】
第一行包含两个整数 (n,k)，表示树的大小与要求找到的路径的边权和。
接下来 (n−1) 行，每行三个整数 (u_i,v_i,w_i)，代表有一条连接 (u_i) 与 (v_i)，边权为 (w_i)
【输出格式】
输出一个整数，表示最小边数量。
如果不存在这样的路径，输出 -1。
题解
点分治 见 http://akdream.tk/post/a082c72e.html/
统计答案就是开一个桶(buc[i])存储 当前子树中 到根路径的边权和为(i)的路径中最少的边数
那么 统计以(x)为根的子树的答案时 依次枚举(x)的每一个儿子 由于在同一个儿子子树中的两个点不能配对 所以我们把这个儿子的子树里的所有点 都拿去((x)的所有前面枚举过的儿子 的子树)组成的桶里匹配 设当前儿子子树中的某个点为(y) 那么更新答案(ans=min(ans,q[y]+buc[k-p[y]]))，(q[y])表示(y)到(x)经过多少条边，(p[y])表示(y)到(x)路径的边权和
吐槽一下 断句难题 组织语言困难综合征
然后把这个儿子的子树放到桶里 也是枚举子树中的所有点 (buc[p[y]]=min(buc[p[y]],q[y]))
ps：(buc[0])是一直等于(0)的 因为这个调了10分钟
ps2：如果在dfs求当前子树中每个点到重心距离时 发现当前节点到重心的距离已经大于(k)了 就直接return 否则容易RE
ps3：每次统计完一次答案后 把桶清空时 不能暴力memset 不然时间复杂度会退化 把这次统计答案更改过的一个个改回(inf)就可以了
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 200005
using namespace std;
typedef long long ll;
inline int read() {
int x = 0, f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
return x * f;
}
const int inf = 0x3f3f3f3f;
int n, k, rt, nowsz, mx;
int head[N], pre[N<<1], to[N<<1], val[N<<1], sz;
int tot[N], dis[N], dis2[N];
int ans;
bool vis[N];
int p[N], q[N], buc[1000005], top, lst;
inline void init() {
buc[0] = 0;
for (int i = 1; i <= k; i++) buc[i] = inf;
ans = inf;
}
inline void addedge(int u, int v, int w) {
pre[++sz] = head[u]; head[u] = sz; to[sz] = v; val[sz] = w;
pre[++sz] = head[v]; head[v] = sz; to[sz] = u; val[sz] = w;
}
void getrt(int x, int fa) {
tot[x] = 1;
int nowmx = -inf;
for (int i = head[x]; i; i = pre[i]) {
int y = to[i];
if (y == fa || vis[y]) continue;
getrt(y, x);
tot[x] += tot[y];
nowmx = max(nowmx, tot[y]);
}
nowmx = max(nowmx, nowsz - tot[x]);
if (nowmx < mx) {
mx = nowmx, rt = x;
}
}
void getdis(int x, int fa) {
if (dis[x] > k) return; //如果x到当前重心的距离已经大于k了 就没必要再搜下去了
p[++top] = dis[x]; q[top] = dis2[x];
for (int i = head[x]; i; i = pre[i]) {
int y = to[i];
if (y == fa || vis[y]) continue;
dis[y] = dis[x] + val[i];
dis2[y] = dis2[x] + 1;
getdis(y, x);
}
}
void calc(int x) {
dis[x] = dis2[x] = 0;
top = 0; buc[0] = 0;
for (int i = head[x]; i; i = pre[i]) {
int y = to[i];
if (vis[y]) continue;
lst = top + 1;
dis[y] = dis[x] + val[i];
dis2[y] = dis2[x] + 1;
getdis(y, x);
//dis[i],p[]: 节点i到x路径的边权和 dis2[i],q[]: 节点i到x路径的边数
for (int j = lst; j <= top; j++) { //把y子树中的节点拿去和前面枚举过的的匹配
ans = min(ans, q[j] + buc[k - p[j]]);
}
for (int j = lst; j <= top; j++) { //把y子树中的所有节点放进桶里
buc[p[j]] = min(buc[p[j]], q[j]);
}
}
for (int i = 1; i <= top; i++) {
buc[p[i]] = inf;
}
}
void divide(int x) {
calc(x);
vis[x] = 1;
for (int i = head[x]; i; i = pre[i]) {
int y = to[i];
if (vis[y]) continue;
mx = inf;
nowsz = tot[y];
getrt(y, 0);
divide(rt);
}
}
int main() {
n = read(); k = read();
init();
for (int i = 1; i < n; i++) {
int u = read() + 1, v = read() + 1, w = read(); //注意输入中节点编号从0开始 不过似乎不影响
addedge(u, v, w);
}
mx = inf;
nowsz = n;
getrt(1, 0);
divide(rt);
printf("%d
", ans == inf ? -1 : ans);
return 0;
}