题解：P11962 [GESP202503 六级] 树上漫步

· · 题解

P11962 树上漫步 题解

思路

部分分

首先考虑暴力，我们可以对每个点进行 dfs 并且进行统计，最后输出，时间复杂度 O(n^2)。

正解

不难发现，从任意结点出发，走偶数步，只能到达深度与出发点深度的差为偶数的结点。

换句话说，出发点与最终到达的结点的深度奇偶性一定相同。

综上，我们可以先以任何一个结点出发，进行一次 dfs，求出每个结点的深度，并将深度为奇数的结点数量用 cnt1 来保存，将深度为偶数的结点用 cnt2 来保存，并将每个结点深度的奇偶性用数组来保存。

最终每个点的答案就是深度与其奇偶性相同的结点数量。

人话：不是 cnt1 就是 cnt2。

时间复杂度 O(n)。

Tips

AC code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5;
int n, cnt1, cnt2;
bool odd[N]; //用odd数组记录每个结点深度的奇偶性
vector<int> e[N];
void dfs(int now, int fa, int dep)
{
    if (dep % 2)
    {
        cnt1++;
        odd[now] = 1;
    }
    else
        cnt2++;
    for (int i = 0; i < e[now].size(); i++)
    {
        int y = e[now][i];
        if (y == fa)
            continue;
        dfs(y, now, dep + 1);
    }
    return;
}
int main()
{
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0, 1);
    for (int i = 1; i <= n; i++)
    {
        if (odd[i])
            cout << cnt1 << " ";
        else
            cout << cnt2 << " ";
    }
    return 0;
}

UPD on 20250910:

修正了两处笔误，感谢 @xue_juanwang_qwq 的指正。