题目大意：给一棵树，每条边有边权。求一条简单路径，权值和等于$K$，且边的数量最小。
题解：点分治，考虑到这是最小值，不满足可减性，于是点分中的更新答案的地方计算重复的部分要做更改，就用一个数组记录前面的答案。更新答案的时候只从已经访问过的部分来转移。
卡点：一个地方没有$return$，导致$RE$
C++ Code：
#include#define maxn 200010#define maxk 1000010const int inf = 0x3f3f3f3f;inline int max(int a, int b) {return a > b ? a : b;}inline int min(int a, int b) {return a < b ? a : b;}int head[maxn], cnt;struct Edge { int to, nxt, w;} e[maxn << 1];inline void add(int a, int b, int c) { e[++cnt] = (Edge) {b, head[a], c}; head[a] = cnt; e[++cnt] = (Edge) {a, head[b], c}; head[b] = cnt;}bool vis[maxn];namespace Center_of_Gravity { int sz[maxn], __nodenum; int root, MIN; #define n __nodenum void __getroot(int u, int fa) { sz[u] = 1; int MAX = 0; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (v != fa && !vis[v]) { __getroot(v, u); sz[u] += sz[v]; MAX = max(MAX, sz[v]); } } MAX = max(MAX, n - sz[u]); if (MAX < MIN) MIN = MAX, root = u; } int getroot(int u, int nodenum = 0) { n = nodenum ? nodenum : sz[u]; MIN = inf; __getroot(u, 0); return root; } #undef n}using Center_of_Gravity::getroot;int n, k, ans = inf;int mindep[maxk], W[maxn], dep[maxn], tot;void getlist(int u, int fa, int val, int __dep) { if (val <= k) ans = min(ans, __dep + mindep[k - val]); else return ; W[++tot] = val, dep[tot] = __dep; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (v != fa && !vis[v]) getlist(v, u, val + e[i].w, __dep + 1); }}inline void init() { W[tot = 1] = 0; dep[tot] = 1; mindep[0] = 0;}void solve(int u) { vis[u] = true; init(); for (int i = head[u], now = 2; i; i = e[i].nxt) { int v = e[i].to; if (!vis[v]) { getlist(v, u, e[i].w, 1); while (now <= tot) { mindep[W[now]] = min(mindep[W[now]], dep[now]); now++; } } } for (int i = 1; i <= tot; i++) mindep[W[i]] = inf; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (!vis[v]) { solve(getroot(v)); } }}int main() { scanf("%d%d", &n, &k); for (int i = 1, a, b, c; i < n; i++) { scanf("%d%d%d", &a, &b, &c); a++, b++; add(a, b, c); } __builtin_memset(mindep, 0x3f, sizeof mindep); solve(getroot(1, n)); if (ans != inf) printf("%d\n", ans); else puts("-1"); return 0;}