~~可能你爆了但是不知道~~
by King_of_gamers @ 2019-01-04 11:20:50
## [记录发错了](https://www.luogu.org/record/show?rid=15190081)
by WAMonster @ 2019-01-04 11:21:20
@[炜哥](/space/show?uid=28810) 不应该先处理RE再处理WA吗qwq
by WAMonster @ 2019-01-04 11:22:23
Orz,可能是您斜挂了
by King_of_gamers @ 2019-01-04 11:22:53
码风好评 ~~我也看不出来哪里错了~~
by Owen_codeisking @ 2019-01-04 11:28:31
debug成这样了:
```cpp
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 202000
#define maxk 10001000
struct edge {
int w, to, next;
} e[maxn << 1];
int head[maxn], dis[maxn], save[maxn], save2[maxn], cnt[maxn], vis[maxn], size[maxn], maxp[maxn], ecnt, sum, depth[maxn];
int get[maxk], get2[maxk];
int n, m, k, ans = 0x3f3f3f3f;
#define isdigit(x) ((x) >= '0' && (x) <= '9')
inline int read() {
int res = 0;
char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) res = (res << 1) + (res << 3) + (c ^ 48), c = getchar();
return res;
}
void adde(int u, int v, int w) {
e[++ecnt] = (edge) {w, v, head[u]};
head[u] = ecnt;
}
int getrt(int x, int fa) {
int rt = 0;
maxp[x] = 0;
size[x] = 1;
for (int i = head[x]; i; i = e[i].next) {
int to = e[i].to;
if (vis[to] || to == fa) continue;
rt = getrt(to, x);
size[x] += size[to];
maxp[x] = max(maxp[x], size[to]);
}
maxp[x] = max(maxp[x], sum - size[x]);
if (maxp[rt] > maxp[x]) rt = x;
return rt;
}
void getdis(int x, int fa) {
save[++save[0]] = dis[x];
cnt[++cnt[0]] = depth[x];
for (int i = head[x]; i; i = e[i].next) {
int to = e[i].to;
if (vis[to] || to == fa) continue;
dis[to] = dis[x] + e[i].w;
depth[to] = depth[x] + 1;
}
}
void work(int x) {
save2[0] = 0;
for (int i = head[x]; i; i = e[i].next) {
int to = e[i].to;
if (vis[to]) continue;
save[0] = cnt[0] = 0;
dis[to] = e[i].w;
depth[to] = 1;
getdis(to, x);
for (int j = 1; j <= save[0]; ++j) {
// get2[save[j]] = min(get2[save[j]], cnt[j]);
if (k >= save[j] && get[k - save[j]])
ans = min(ans, get2[k - save[j]] + cnt[j]);
}
for (int j = 1; j <= save[0]; ++j) {
get[save[j]] = 1, save2[++save2[0]] = save[j];
get2[save[j]] = min(get2[save[j]], cnt[j]);
}
}
for (int i = 1; i <= save2[0]; ++i) get[save2[i]] = 0, get2[save2[i]] = 0x3f3f3f3f;
}
void dfs(int x) {
vis[x] = get[0] = 1;
get2[0] = 0;
work(x);
for (int i = head[x]; i; i = e[i].next) {
int to = e[i].to;
if (vis[to]) continue;
maxp[0] = 0x3f3f3f3f;
sum = size[to];
dfs(getrt(to, 0));
}
}
int main() {
memset(get2, 0x3f, sizeof(get2));
n = read(), k = read();
for (int i = 1; i < n; ++i) {
int u = read(), v = read(), w = read();
adde(u + 1, v + 1, w);
adde(v + 1, u + 1, w);
}
maxp[0] = sum = n;
dfs(getrt(1, 0));
if (ans == 0x3f3f3f3f) puts("-1");
else printf("%d\n", ans);
return 0;
}
```
但还是40。。输出还是`-1`。。
求dalao帮帮本蒟蒻吧qwq
by WAMonster @ 2019-01-04 21:54:08
解决了。。。原因:`getdis`函数没递归。。。
by WAMonster @ 2019-01-05 08:44:52
有毒啊。。。
by duyi @ 2019-02-05 11:50:16