简答题
偏难
#20456
树上漫步 时间限制:1 s,内存限制:512 MB 【问题描述】 小 A 有一棵 n 个结点的树,这些结点依次以 1、2、……、n标号。 小 A 想在这棵树上漫…
树上漫步
时间限制:1 s,内存限制:512 MB
【问题描述】
小 A 有一棵 n 个结点的树,这些结点依次以 1、2、……、n标号。
小 A 想在这棵树上漫步。具体来说,小 A 会从树上的某个结点出发,每一步可以移动到与当前结点相邻的结点,并且小 A 只会在偶数步(可以是零步)后结束漫步。
现在小 A 想知道,对于树上的每个结点,从这个结点出发开始漫步,经过偶数步能结束漫步的结点有多少个(可以经过重复的节点)。
【输入描述】
第一行,一个正整数 n。
接下来 n - 1 行,每行两个整数 ui、vi,表示树上有一条连接结点 ui 和结点 vi 的边。
【输出描述】
一行, n 个整数,第 i 个整数表示从结点 i 出发开始漫步,能结束漫步的结点数量。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于 20% 的测试点,保证 1<=n<=1000。
对于所有测试点,保证 1<=n<=200000。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5;
const int E = N << 1;
int n;
int h[N], to[E], nx[E], et;
int cnt[N], bel[N];
void ae(int u, int v) {
et++;
to[et] = v;
nx[et] = h[u];
h[u] = et;
}
void dfs(int u, int c, int f) {
bel[u] = c;
cnt[c]++;
for (int i = h[u]; i; i = nx[i])
if (to[i] != f)
dfs(to[i], c ^ 1, u);
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
ae(u, v);
ae(v, u);
}
dfs(1, 0, 0);
for (int i = 1; i <= n; i++)
printf("%d%c", cnt[bel[i]], " \n"[i == n]);
return 0;
}</pre>
这道题暂未补解析。