蒟蒻表示看不懂
by AFO蒟蒻选手 @ 2019-01-22 20:54:16
您应该是dfs中去dfs(root) 否则白求root了，而且复杂度不对
by 一枚 @ 2019-01-22 20:58:14
@[ezoixx118](/space/show?uid=30541) 您应该是dfs中去dfs(root) 否则白求root了，而且复杂度不对
by 一枚 @ 2019-01-22 20:58:32
@[一枚](/space/show?uid=31079) 哦，我sb打错了，但p4178数据未免太水了
by ezoixx118 @ 2019-01-22 20:59:34
仍然t了，https://www.luogu.org/recordnew/show/15605204
@[一枚](/space/show?uid=31079)
by ezoixx118 @ 2019-01-22 21:01:58
@[ezoixx118](/space/show?uid=30541) 17个点是1~50000 的一条链，k=500 答案是49500
by 一枚 @ 2019-01-22 22:02:26
@[ezoixx118](/space/show?uid=30541) 查出来了，你maxsiz没置0
by 一枚 @ 2019-01-22 22:21:15
已过，谢谢dalao，@[一枚](/space/show?uid=31079)
by ezoixx118 @ 2019-01-23 08:14:08
同是T掉最后一个点，请问dalao是哪里写挂了啊
by 祥瑞御免 @ 2019-02-21 22:22:14
如果有空的话可以帮我也看一看吗蒟蒻感激不尽
```cpp
#include <bits/stdc++.h>
using namespace std;
#define N 50100
int n, k, sum, cnt, tot, root;
int f[N], sz[N], dis[N], vis[N];
int head[N], to[N << 1], nxt[N << 1];
long long ans;
inline void add(int x, int y) {
to[++cnt] = y, nxt[cnt] = head[x], head[x] = cnt;
}
void getrt(int now, int fa) {
sz[now] = 1;
for (int i = head[now]; i; i = nxt[i]) {
if (to[i] == fa) continue;
getrt(to[i], now);
sz[now] += sz[to[i]], f[now] = max(f[now], sz[to[i]]);
}
f[now] = max(f[now], sum - sz[now]);
if (f[now] < f[root]) root = now;
}
void dfs(int now, int fa, int dep) {
dis[++tot] = dep;
for (int i = head[now]; i; i = nxt[i]) {
if (to[i] == fa || vis[to[i]]) continue;
dfs(to[i], now, dep + 1);
}
}
inline int calc(int now, int lst) {
int ret = 0; tot = 0;
dfs(now, 0, lst);
sort(dis + 1, dis + tot + 1);
for (int i = 1; i <= tot; ++i) {
if (2 * dis[i] > k) break;
ret += upper_bound(dis + i + 1, dis + tot + 1, k - dis[i]) - lower_bound(dis + i + 1, dis + tot + 1, k - dis[i]);
}
return ret;
}
void solve(int now) {
ans += calc(now, 0), vis[now] = 1;
for (int i = head[now]; i; i = nxt[i]) {
if (!vis[to[i]]) {
ans -= calc(to[i], 1);
sum = sz[to[i]], root = 0;
getrt(to[i], now), solve(root);
}
}
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1, x, y; i < n; ++i) {
scanf("%d%d", &x, &y);
add(x, y), add(y, x);
}
sum = f[0] = n;
getrt(1, 0), solve(root);
printf("%I64d", ans);
return 0;
}
```
by 祥瑞御免 @ 2019-02-21 22:24:00