- #include#include#include#include#include using namespace std;
- const int N = 2e5 + 5,
- K = 1e6 + 5,
- INF = 1e9;
- inline int read() {
- char c = getchar();
- int x = 0,
- f = 1;
- while (c < '0' || c > '9') {
- if (c == ' - ') f = -1;
- c = getchar();
- }
- while (c >= '0' && c <= '9') {
- x = x * 10 + c - '0';
- c = getchar();
- }
- return x * f;
- }
- int n,
- k,
- u,
- v,
- w;
- struct edge {
- int v,
- w,
- ne;
- }
- e[N << 1];
- int h[N],
- cnt;
- inline void ins(int u, int v, int w) {
- cnt++;
- e[cnt].v = v;
- e[cnt].w = w;
- e[cnt].ne = h[u];
- h[u] = cnt;
- cnt++;
- e[cnt].v = u;
- e[cnt].w = w;
- e[cnt].ne = h[v];
- h[v] = cnt;
- }
- int size[N],
- f[N],
- rt,
- vis[N],
- sum;
- void dfsRt(int u, int fa) {
- size[u] = 1;
- f[u] = 0;
- for (int i = h[u]; i; i = e[i].ne) {
- int v = e[i].v;
- if (vis[v] || v == fa) continue;
- dfsRt(v, u);
- size[u] += size[v];
- f[u] = max(f[u], size[v]);
- }
- f[u] = max(f[u], sum - size[u]);
- if (f[u] u;
- }
- int deep[N],
- d[K],
- c[N],
- ans = INF;
- void cal(int u, int fa) {
- if (deep[u] <= k) ans = min(ans, d[k - deep[u]] + c[u]);
- for (int i = h[u]; i; i = e[i].ne) {
- int v = e[i].v;
- if (vis[v] || v == fa) continue;
- deep[v] = deep[u] + e[i].w;
- c[v] = c[u] + 1;
- cal(v, u);
- }
- }
- void add(int u, int fa) {
- if (deep[u] <= k) d[deep[u]] = min(d[deep[u]], c[u]);
- for (int i = h[u]; i; i = e[i].ne) {
- int v = e[i].v;
- if (vis[v] || v == fa) continue;
- add(v, u);
- }
- }
- void recover(int u, int fa) {
- if (deep[u] <= k) d[deep[u]] = INF;
- for (int i = h[u]; i; i = e[i].ne) {
- int v = e[i].v;
- if (vis[v] || v == fa) continue;
- recover(v, u);
- }
- }
- void dfsSol(int u) { //printf("sol %d\n",u);
- vis[u] = 1;
- d[0] = 0; //must d[0]=0!!!!!!!!!!!!!!!!
- for (int i = h[u]; i; i = e[i].ne) {
- int v = e[i].v;
- if (vis[v]) continue;
- deep[v] = e[i].w;
- c[v] = 1;
- cal(v, u);
- add(v, u);
- }
- for (int i = h[u]; i; i = e[i].ne) {
- int v = e[i].v;
- if (vis[v]) continue;
- recover(v, u);
- }
- for (int i = h[u]; i; i = e[i].ne) {
- int v = e[i].v;
- if (vis[v]) continue;
- sum = size[v];
- rt = 0;
- dfsRt(v, 0);
- v = rt;
- dfsSol(v);
- }
- }
- int main() {
- //freopen("in.txt","r",stdin);
- n = read();
- k = read();
- for (int i = 1; i <= k; i++) d[i] = INF;
- for (int i = 1; i1, v = read() + 1, w = read(), ins(u, v, w); sum = n; f[0] = INF; rt = 0; dfsRt(1, 0); dfsSol(rt); printf("%d", ans == INF ? -1 : ans);
- }
来源: