专栏文章
题解:P11962 [GESP202503 六级] 树上漫步
P11962题解参与者 4已保存评论 5
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @miptxktc
- 此快照首次捕获于
- 2025/12/03 17:53 3 个月前
- 此快照最后确认于
- 2025/12/03 17:53 3 个月前
P11962 树上漫步 题解
思路
部分分
首先考虑暴力,我们可以对每个点进行 dfs 并且进行统计,最后输出,时间复杂度 。
正解
不难发现,从任意结点出发,走偶数步,只能到达深度与出发点深度的差为偶数的结点。
换句话说,出发点与最终到达的结点的深度奇偶性一定相同。
综上,我们可以先以任何一个结点出发,进行一次 dfs,求出每个结点的深度,并将深度为奇数的结点数量用 来保存,将深度为偶数的结点用 来保存,并将每个结点深度的奇偶性用数组来保存。
最终每个点的答案就是深度与其奇偶性相同的结点数量。
人话:不是 就是 。
时间复杂度 。
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 条评论,欢迎与作者交流。
正在加载评论...