【题目描述】
给一棵树,每条边有权.求一条简单路径,权值和等于$k$,且边的数量最小。

【输入格式】
第一行包含两个整数$n,k$,表示树的大小与要求找到的路径的边权和。

接下来$n-1$行,每行三个整数$u_i,v_i,w_i$,代表有一条连接$u_i$与$v_i$,边权为$w_i$

【输出格式】
输出一个整数,表示最小边数量。

如果不存在这样的路径,输出 -1

题解

点分治 见 https://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$就可以了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#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\n", ans == inf ? -1 : ans);
return 0;
}

评论