【题目描述】
【输入格式】
接下来$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分钟
代码 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 ; 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); for (int j = lst; j <= top; j++) { ans = min(ans, q[j] + buc[k - p[j]]); } for (int j = lst; j <= top; j++) { 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(); addedge(u, v, w); } mx = inf; nowsz = n; getrt(1 , 0 ); divide(rt); printf ("%d\n" , ans == inf ? -1 : ans); return 0 ; }
