树戍数点

出了一道题, 天知道怎么出出来的……
应该是写了一个错误的代码扔了太可惜了然后就出成题了.

Description

有一棵有$n$个点的树, 树上边的长度为1, 问树上距离一个点$u$距离为$1, 2, \cdots$的点各有多少个.

Input

一行一个整数$n$, 表示树上点的个数.
后面$n-1$行每行两个整数$u,v$表示一条边.
后面一个整数$m$, 下面1行$m$个数$u$, 表示需要求出$u$的答案.

Output

$m$行一行若干个数, 为树上距离一个点$u$距离为$1, 2, \cdots$的点各有多少个.

Other

  • 10%, $n\le100, m \le 10$
  • 10%, $n\le100, m \le 100$
  • 10%, $n\le 5000, m\le10$
  • 20%, $n\le 2000, m\le 500$
  • 40%, $n\le 10000, m\le 10000$

暂时隐藏题解和代码.
<!–

Solution


设$f_{u,h}$表示$u$上方和它距离为$h$的点有多少个.
设$g_{u,h}$表示$g$下方和它距离为$h$的点有多少个.
$$
f_{u,h}=\begin{cases}
\sum_{u\rightarrow v}f_{v,h-1}&,uh>0\\
1&,uh=0
\end{cases}
$$
$$
g_{u,h}=\begin{cases}
f_{fa,h-1}-f_{u,h-2}+g_{fa,h-1}&,h>1\\
1&,h=1
\end{cases}
$$

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
#include <set>
#include <queue>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5005;
const int inf = 0x3f3f3f3f;
struct Edge {
int v, nxt;
} e[N << 1];
int head[N], tot;
void AddEdge(int u, int v) {
e[++tot] = (Edge) {v, head[u]}; head[u] = tot;
e[++tot] = (Edge) {u, head[v]}; head[v] = tot;
}
int res[N];
int depth[N];
int top[N][N];
int dep[N][N];
void GetDown(int u, int fa) {
dep[u][0] = 1;
for (int i = head[u]; i; i = e[i].nxt) {
if (e[i].v == fa) continue;
GetDown(e[i].v, u);
dep[u][1] += dep[e[i].v][0];
for (int high = 1; high <= 5; high += 1)
dep[u][high + 1] += dep[e[i].v][high];
}
}
void GetUPPP(int u, int fa) {
top[u][0] = 0, top[u][1] = fa > 0;
for (int i = head[u]; i; i = e[i].nxt) {
if (e[i].v == fa) continue;
for (int tmp = 1; tmp <= 5; tmp += 1)
top[e[i].v][tmp + 1] += dep[u][tmp] - dep[e[i].v][tmp - 1] + top[u][tmp];
GetUPPP(e[i].v, u);
}
}
int main () {
int n; scanf("%d", &n);
for (int i = 1, u, v; i < n; i += 1) {
scanf("%d%d", &u, &v);
AddEdge(u, v);
}
int m; scanf("%d", &m);
GetDown(1, 0), GetUPPP(1, 0);
for (int i = 1, u; i <= m; i += 1) {
scanf("%d", &u);
for (int j = 1; j <= n; j += 1)
if (dep[u][j] + top[u][j])
printf("%d ", dep[u][j] + top[u][j]);
else break;
puts(" ");
}
return 0;
}

–>

-------------本文结束感谢您的阅读-------------