[COGS 2722][CodeforcesEduR22C] The tag game

OI
  1. 1. 题目描述
  2. 2. 思路
    1. 2.1. 向根节点方向走
    2. 2.2. 向叶子方向走
    3. 2.3. 不动
  3. 3. 解决方案
  4. 4. 代码
  5. 5. 来源

题目描述

原题地址: COGS Codeforces

思路

Bob的移动策略有三种:

向根节点方向走

T1

如图,经过迂回之后可以到达更深的节点

向叶子方向走

T2

如图,可以苟且延长一些寿命

不动

当到达叶子节点时只能坐以待毙了

解决方案

预处理出来每个点的深度,和以每个点为根的子树的最大深度。

然后开始模拟,如果Bob能比Alice先到达某节点,就用这个节点更新答案,显然$ans=2deepth(u)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
const int maxn = ((int)1e5 << 1) + 10;
vector<int> g[maxn];
int f[maxn], d[maxn], md[maxn];
int n, x, ans;
void dfs(int cur, int fr, int de)
{
d[cur]= md[cur] = de, f[cur] = fr;
for (int i = 0; i < g[cur].size(); ++i)
{
if (fr == g[cur][i]) continue;
dfs(g[cur][i], cur, de + 1);
md[cur] = max(md[cur], md[g[cur][i]]);
}
}
int main()
{
freopen("taggame.in","r",stdin);
freopen("taggame.out","w",stdout);
cin >> n >> x;
for (int i = 1; i < n; ++i)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0, 0);
ans = (md[x] << 1);
for (int i = 0, j = x; ; ++i, j = f[j])
{
if (i < d[j]) ans = max(ans, (md[j] << 1));
else break;
}
cout << ans << endl;
}

来源

官方题解