专栏文章

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

P11962题解参与者 4已保存评论 5

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@miptxktc
此快照首次捕获于
2025/12/03 17:53
3 个月前
此快照最后确认于
2025/12/03 17:53
3 个月前
查看原文

P11962 树上漫步 题解

思路

部分分

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

正解

不难发现,从任意结点出发,走偶数步,只能到达深度与出发点深度的差为偶数的结点。
换句话说,出发点与最终到达的结点的深度奇偶性一定相同。
综上,我们可以先以任何一个结点出发,进行一次 dfs,求出每个结点的深度,并将深度为奇数的结点数量用 cnt1cnt1 来保存,将深度为偶数的结点用 cnt2cnt2 来保存,并将每个结点深度的奇偶性用数组来保存。
最终每个点的答案就是深度与其奇偶性相同的结点数量。
人话:不是 cnt1cnt1 就是 cnt2cnt2
时间复杂度 O(n)O(n)

Tips

  • 注意题目要求,可以经过重复的结点,所以在统计数量时不需要去重。

AC code

CPP
#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的指正。

评论

5 条评论,欢迎与作者交流。

正在加载评论...