简答题 偏难
#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】

3
1 3
2 3

【样例输出1】

2 2 1

【样例输入2】

4
1 3
3 2
4 3

【样例输出2】

3 3 1 3

【数据范围】

对于 20% 的测试点,保证 1<=n<=1000。

对于所有测试点,保证 1<=n<=200000。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; #include &lt;algorithm&gt; using namespace std; const int N = 2e5 + 5; const int E = N &lt;&lt; 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", &amp;n);     for (int i = 1; i &lt; n; i++) {         int u, v;         scanf("%d%d", &amp;u, &amp;v);         ae(u, v);         ae(v, u);     }     dfs(1, 0, 0);     for (int i = 1; i &lt;= n; i++)         printf("%d%c", cnt[bel[i]], " \n"[i == n]);     return 0; }</pre>
这道题暂未补解析。