算法1
(暴力点分治)
C++ 代码
#include <bits/stdc++.h>
#define For(i, a, b) for(register int i = (a); i <= (b); ++i)
#define Rof(i, a, b) for(register int i = (a); i >= (b); --i)
#define LL long long
#define MaxN 200100
#define INF 0x3f3f3f3f
using namespace std;
int N, K, Head[MaxN], Judge[1000001], Num[MaxN], Cnt = 1, MaxP, Root, MR, u, v, w, Siz[MaxN], Ans = INF, Sum, Q[MaxN], Rem[MaxN], Rem_Cnt, Dis[MaxN];
bool Vis[MaxN];
struct Xjh {int Ver, Next, Weight;} E[MaxN << 1];
void Add_Edge(int u, int v, int w) {E[++Cnt].Ver = v, E[Cnt].Weight = w, E[Cnt].Next = Head[u], Head[u] = Cnt;}
void Get_Root(int u, int f) {
Siz[u] = 1; int MaxP = 0;
for(int i = Head[u], v; i; i = E[i].Next) {
if(Vis[v = E[i].Ver] || v == f) continue;
Get_Root(v, u); Siz[u] += Siz[v]; MaxP = max(MaxP, Siz[v]);
}
MaxP = max(MaxP, Sum - Siz[u]);
if(MaxP < MR) MR = MaxP, Root = u;
}
void Get_Dis(int u, int f, int d) {
Rem[++Rem_Cnt] = Dis[u]; Num[Rem_Cnt] = d;
for(int i = Head[u], v; i; i = E[i].Next) {
if(Vis[v = E[i].Ver] || v == f) continue;
Dis[v] = Dis[u] + E[i].Weight; Get_Dis(v, u, d + 1);
}
}
void Calc(int u) {
Judge[0] = 0; int Tot = 0;
for(int i = Head[u], v; i; i = E[i].Next) {
if(Vis[v = E[i].Ver]) continue;
Rem_Cnt = 0; Dis[v] = E[i].Weight; Get_Dis(v, u, 1);
For(j, 1, Rem_Cnt) {
if(Rem[j] > K) continue;
if(Judge[K - Rem[j]] == -1) continue;
Ans = min(Ans, Num[j] + Judge[K - Rem[j]]);
}
For(j, 1, Rem_Cnt) if(Rem[j] <= K) Judge[Rem[j]] = (Judge[Rem[j]] == -1 ? Num[j] : min(Num[j], Judge[Rem[j]])), Q[++Tot] = Rem[j];
}
For(i, 1, Tot) if(Q[i] <= K) Judge[Q[i]] = -1;
}
void Solve(int u) {
Vis[u] = 1; Calc(u);
for(int i = Head[u], v; i; i = E[i].Next) {
if(Vis[v = E[i].Ver]) continue;
Sum = MR = Siz[v]; Get_Root(v, 0); Solve(Root);
}
}
int main() {
memset(Judge, -1, sizeof(Judge));
scanf("%d%d", &N, &K); For(i, 1, N - 1) scanf("%d%d%d", &u, &v, &w), ++u, ++v, Add_Edge(u, v, w), Add_Edge(v, u, w);
MR = Sum = N; Get_Root(1, 0); Solve(Root);
if(Ans == INF) puts("-1"); else printf("%d\n", Ans);
return 0;
}