D&C on Tree.

Description

Given a weighed tree and calculate a simple path whose sum of values is $K$ with minimum edges.

Solution

Just brute force:)

When at a key point, do DFS in every subtree, update the answer with data already exist in the bucket. Then update the data in bucket.

Before exit the key point, clear the bucket.

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
 
using namespace std;
 
const int maxn = 2e+5 + 5;
const int maxv = 1e+6 + 5;
const int inf = 0x3f3f3f3f;
 
struct edge {
  int to, nxt, v;
}e[maxn << 1];
int n, k, ptr, lnk[maxn], glbmn;
int bkt[maxv], ans, sum, rt, vis[maxn], mxsiz[maxn];
int dis[maxn], edg[maxn], siz[maxn];
 
inline void add(int bgn, int end, int val) {
  e[++ptr] = (edge){end, lnk[bgn], val};
  lnk[bgn] = ptr;
}
inline int rd() {
  register int x = 0, c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return x;
}
void getroot(int x, int fa) {
  siz[x] = 1; mxsiz[x] = 0;
  for (int p = lnk[x]; p; p = e[p].nxt) {
    int y = e[p].to;
    if (y == fa || vis[y]) continue;
    getroot(y, x);
    siz[x] += siz[y];
    if (siz[y] > mxsiz[x]) mxsiz[x] = siz[y];
  }
  mxsiz[x] = max(mxsiz[x], sum - mxsiz[x]);
  if (mxsiz[x] < mxsiz[rt]) rt = x;
}
void calc(int x, int fa) {
  if (dis[x] <= k) ans = min(ans, edg[x] + bkt[k - dis[x]]);
  for (int p = lnk[x]; p; p = e[p].nxt) {
    int y = e[p].to;
    if (y == fa || vis[y]) continue;
    dis[y] = dis[x] + e[p].v; 
    edg[y] = edg[x] + 1;
    calc(y, x);
  }
}
void chg(int x, int fa, int tag) {
  if (dis[x] <= k) {
    if (tag) bkt[dis[x]] = min(bkt[dis[x]], edg[x]);
    else bkt[dis[x]] = inf;
  }
  for (int p = lnk[x]; p; p = e[p].nxt) {
    int y = e[p].to;
    if (y == fa || vis[y]) continue;
    chg(y, x, tag);
  }
}
void solve(int x) {
  vis[x] = 1;
  bkt[0] = 0;
  for (int p = lnk[x]; p; p = e[p].nxt) {
    int y = e[p].to;
    if (vis[y]) continue;
    dis[y] = e[p].v;
    edg[y] = 1;
    calc(y, 0);
    chg(y, 0, 1);
  }
  for (int p = lnk[x]; p; p = e[p].nxt) {
    int y = e[p].to;
    if (vis[y]) continue;
    chg(y, 0, 0);
  }
  for (int p = lnk[x]; p; p = e[p].nxt) {
    int y = e[p].to;
    if (vis[y]) continue;
    rt = 0; sum = siz[y];
    getroot(y, 0);
    solve(rt);
  }
}
 
int main() {
  n = rd(); k = rd();
  mxsiz[0] = n;
  int u, v, w;
  for (register int i = 1; i <= k; ++i) bkt[i] = n;
  for (register int i = 1; i < n; ++i) {
    u = rd(); v = rd(); w = rd();
    u++; v++;
    add(u, v, w);
    add(v, u, w);
  }
  ans = sum = n;
  getroot(1, 0);
  solve(rt);
  if (ans < n) {
    printf("%d\n", ans);
  } else puts("-1");
  return 0;
}