CF1452G Game On Tree
题目来源：Codeforces, Educational Codeforces Round 98 (Rated for Div. 2), CF1452G Game On Tree
题目大意
Alice 和 Bob 在玩一个游戏。他们有一棵由 (n) 个结点组成的树。一开始，Bob 有 (k) 个卡片，其中第 (i) 个卡片位于结点 (a_i)（注意：所有的结点都是唯一的）。在游戏开始之前，Alice 将在这棵树的一个结点上放置一个卡片。
这个游戏由一些回合组成。每个回合都将有以下事件发生（完全按照以下顺序）：
- Alice 可以把她的卡片移到相邻的结点，或者不移动；
- 对于 Bob 的每一张卡片，他可以把这张卡片移到相邻的结点，或者不移动。注意：每个卡片的选择都是独立的。
当 Alice 的卡片与 Bob 的任意一张（或多张）卡片在同一结点时，游戏结束。（Bob 自己的多张卡片可以置于同一结点上，即使它们的初始位置一定是不同的）。
Alice 希望游戏回合越多越好，Bob则相反。如果某回合中间游戏结束（即 Alice 把卡片移到了有 Bob 卡片的结点上），这回合依然算入总回合数。
对于每个结点，计算 Alice 一开始将卡片放在该结点时游戏将持续的回合数。
数据范围：(2leq nleq 2 imes 10^5)，(1leq k < n)。
本题题解
设树上两点 (u,v) 间的距离为 ( ext{dis}(u,v))。
考虑对某个 Alice 的起点 (a) 求答案。先把 (a) 提作树根。
设 Bob 的所有起点中，离 (u) 最近的点与 (u) 的距离为 ( ext{disBob}(u))。
考虑 Bob 的移动策略，显然他一定让所有点同时向当前 Alice 所在的位置走。
与此同时 Alice 要避免被 Bob 追到，她会向她能到达的点里，( ext{disBob}(u)) 最大的点走。“她能到达的点”指的是在 Alice 从起点 (a) 走到这个点的过程中，不会被 Bob 逮到。具体来说，一个点 (u) 是“能到达的”，当且仅当 ( ext{dis}(a,u)leq ext{disBob}(u)) 且对于 (a) 到 (u) 路径上除 (u) 外所有点 (v)，( ext{dis}(a,v) < ext{disBob}(v))。
对所有点 (uin[1,n]) 预处理出 ( ext{disBob}(u))，可以通过树形 DP + 换根预处理，时间复杂度 (O(n))。
然后对每个 (a) 求答案，只需要从 (a) 出发 dfs 一遍，求出所有“能到达的点” (u) 的 ( ext{disBob}(u)) 的最大值。总时间复杂度 (O(n^2))。无法通过本题。
考虑优化上述过程。将点按 ( ext{disBob}(u)) 从小到大排成一个序列 (p_1,p_2,dots,p_n)（(p) 是一个 (1dots n) 的排列且 ( ext{disBob}(p_1)leq ext{disBob}(p_2)leq dotsleq ext{disBob}(p_n))。对每个点 (a)，在这个序列上二分答案。问题转化为求 (p_{ ext{mid}+1},dots ,p_{r}) 中，是否存在点 (p_i) 是 (a) “能到达”的。
单独二分似乎难以操作。我们对所有 (a) 整体二分。具体来说，我们定义一个递归的函数 ( ext{solve}(Q,l,r)) 表示 (Q) 集合里的这些 (a)，答案都在 (l,r) 之间。若 (l=r)，则直接记下答案，然后返回。否则设 ( ext{mid} = lfloorfrac{l+r}{2} floor)。我们对 (Q) 集合里的所有 (a)，判断：集合 (P = {p_{ ext{mid}+1},dots,p_{r}}) 中，是否存在点 (p_i) 是 (a) “能到达”的。
要一次性判断所有 (a)，可以对 (Qcup P) 这些点，建出虚树。然后做树形 DP。设 (f(u)) 表示 (u) 子树里所有 (P) 集合里的点 (v) 中，( ext{dis}(v,u) - ext{disBob}(v)) 的最小值。
对于根节点 ( ext{root})，如果 (f( ext{root}) < 0)，则 ( ext{root}) 的答案在 ([ ext{mid}+1,r]) 中；如果 (f( ext{root}) > 0) 则它的答案在 ([l, ext{mid}]) 中。换根后，即可对所有点分别做出这样的判断。然后将 (Q) 划分为两个集合 (Q_L,Q_R)，分别递归调用：( ext{solve}(Q_L,l, ext{mid}))，( ext{solve}(Q_R, ext{mid} + 1, r)) 即可。
需要注意的是，(f( ext{root}) = 0) 的情况是比较特殊的。它能放在 (Q_R)，当且仅当存在一个点 (uin P)，满足 ( ext{dis}(u, ext{root}) = ext{disBob}(u))，且 (u) 向 ( ext{root}) 方向的儿子子树里（也就是以 ( ext{root}) 为根时，(u) 子树以外的所有点），不存在一个 Bob 的起点 (b) 使得 ( ext{dis}(b,u) = ext{disBob}(u))。这也可以通过做一个类似的树形 DP：只要 (u) 的子树外，存在到 (u) 距离等于 ( ext{disBob}(u)) 的 Bob 的起点，我们就不让 (u) 对父亲的 DP 值产生贡献（假装 (u) 不在 (P) 集合里）。然后再换根一次即可。
发现在递归的过程中，每个节点只会递归 (O(log n)) 层（因为是个二分），每层里要建虚树，所以总时间复杂度 (O(nlog^2n))。
参考代码
// problem: CF1452G
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template<typename T> inline void ckmax(T& x, T y) { x = (y > x ? y : x); }
template<typename T> inline void ckmin(T& x, T y) { x = (y < x ? y : x); }
/* --------------- fast io --------------- */ // begin
namespace Fread {
const int SIZE = 1 << 21;
char buf[SIZE], *S, *T;
inline char getchar() {
if (S == T) {
T = (S = buf) + fread(buf, 1, SIZE, stdin);
if (S == T) return EOF;
}
return *S++;
}
} // namespace Fread
namespace Fwrite {
const int SIZE = 1 << 21;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
fwrite(buf, 1, S - buf, stdout);
S = buf;
}
inline void putchar(char c) {
*S++ = c;
if (S == T) flush();
}
struct NTR {
~ NTR() { flush(); }
}ztr;
} // namespace Fwrite
#ifdef ONLINE_JUDGE
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
#endif
namespace Fastio {
struct Reader {
template<typename T>
Reader& operator >> (T& x) {
char c = getchar();
T f = 1;
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
x = 0;
while (c >= '0' && c <= '9') {
x = x * 10 + (c - '0');
c = getchar();
}
x *= f;
return *this;
}
Reader& operator >> (char& c) {
c = getchar();
while (c == '
' || c == ' ') c = getchar();
return *this;
}
Reader& operator >> (char* str) {
int len = 0;
char c = getchar();
while (c == '
' || c == ' ') c = getchar();
while (c != '
' && c != ' ') {
str[len++] = c;
c = getchar();
}
str[len] = ' ';
return *this;
}
Reader(){}
}cin;
const char endl = '
';
struct Writer {
template<typename T>
Writer& operator << (T x) {
if (x == 0) { putchar('0'); return *this; }
if (x < 0) { putchar('-'); x = -x; }
static int sta[45];
int top = 0;
while (x) { sta[++top] = x % 10; x /= 10; }
while (top) { putchar(sta[top] + '0'); --top; }
return *this;
}
Writer& operator << (char c) {
putchar(c);
return *this;
}
Writer& operator << (char* str) {
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer& operator << (const char* str) {
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer(){}
}cout;
} // namespace Fastio
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
/* --------------- fast io --------------- */ // end
const int MAXN = 2e5;
const int INF = 1e9;
int n, K, a[MAXN + 5];
bool mark[MAXN + 5];
struct EDGE { int nxt, to; } edge[MAXN * 2 + 5];
int head[MAXN + 5], tot;
inline void add_edge(int u, int v) { edge[++tot].nxt = head[u]; edge[tot].to = v; head[u] = tot; }
namespace TreeChainPartition {
int fa[MAXN + 5], sz[MAXN + 5], son[MAXN + 5], dep[MAXN + 5];
void dfs1(int u) {
sz[u] = 1;
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].to;
if (v == fa[u])
continue;
fa[v] = u;
dep[v] = dep[u] + 1;
dfs1(v);
sz[u] += sz[v];
if (!son[u] || sz[v] > sz[son[u]])
son[u] = v;
}
}
int top[MAXN + 5], dfn[MAXN + 5], ofn[MAXN + 5], rev[MAXN + 5], cnt_dfn;
void dfs2(int u, int t) {
top[u] = t;
dfn[u] = ++cnt_dfn;
rev[cnt_dfn] = u;
if (son[u])
dfs2(son[u], t);
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].to;
if (v == fa[u] || v == son[u])
continue;
dfs2(v, v);
}
ofn[u] = cnt_dfn;
}
int get_lca(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]])
swap(u, v);
u = fa[top[u]];
}
return (dep[u] < dep[v]) ? u : v;
}
int jump(int u, int _anc) {
while (top[u] != top[_anc]) {
if (fa[top[u]] == _anc) {
return top[u];
}
u = fa[top[u]];
}
return rev[dfn[_anc] + 1];
}
void init() {
dfs1(1);
dfs2(1, 1);
}
} // namespace TreeChainPartition
using TreeChainPartition :: dep;
using TreeChainPartition :: dfn;
using TreeChainPartition :: get_lca;
using TreeChainPartition :: jump;
int bob_dis[MAXN + 5];
int ans[MAXN + 5];
vector<int> vec[MAXN + 5];
void dfs1(int u, int fa) {
vec[u].pb(INF);
if (mark[u]) {
vec[u].pb(0);
}
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].to;
if (v == fa)
continue;
dfs1(v, u);
if (bob_dis[v] != INF)
vec[u].pb(bob_dis[v] + 1);
}
sort(vec[u].begin(), vec[u].end());
bob_dis[u] = vec[u][0];
}
int bob_dis_from_fa[MAXN + 5];
bool flag[MAXN + 5];
void dfs2(int u, int fa) {
if (fa) {
int ff;
if (bob_dis[u] + 1 == vec[fa][0]) {
ff = vec[fa][1];
} else {
ff = vec[fa][0];
flag[u] = 1;
}
bob_dis_from_fa[u] = ff;
if (ff != INF) {
vec[u].pb(ff + 1);
}
sort(vec[u].begin(), vec[u].end());
bob_dis[u] = vec[u][0];
}
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].to;
if (v == fa)
continue;
dfs2(v, u);
}
}
int nodes_sorted_by_bob_dis[MAXN + 5];
bool cmp_by_bob_dis(int u, int v) { return bob_dis[u] < bob_dis[v]; }
struct VIREDGE { int nxt, to, w; } vir_edge[MAXN * 2 + 5]; // 虚树
int vir_head[MAXN + 5], vir_tot;
int tim[MAXN + 5], TIM;
inline void vir_add_edge(int u, int v, int w) {
if (tim[u] < TIM) {
tim[u] = TIM;
vir_head[u] = 0; // 懒惰清空
}
if (tim[v] < TIM) {
tim[v] = TIM;
vir_head[v] = 0;
}
vir_edge[++vir_tot].nxt = vir_head[u];
vir_edge[vir_tot].to = v;
vir_edge[vir_tot].w = w;
vir_head[u] = vir_tot;
}
int sta[MAXN + 5], top;
int nodes_sorted_by_dfn[MAXN * 2 + 5], cnt;
bool cmp_by_dfn(int u, int v) { return dfn[u] < dfn[v]; }
void add_node(int u) {
if (!top) {
sta[++top] = u;
return;
}
int lca = get_lca(sta[top], u);
if (lca == sta[top]) {
sta[++top] = u;
return;
}
while (top >= 2 && dep[sta[top - 1]] >= dep[lca]) {
vir_add_edge(sta[top - 1], sta[top], dep[sta[top]] - dep[sta[top - 1]]);
--top;
}
if (sta[top] == lca) {
sta[++top] = u;
return;
}
vir_add_edge(lca, sta[top], dep[sta[top]] - dep[lca]);
sta[top] = lca;
sta[++top] = u;
}
int fw[MAXN + 5];
int f[MAXN + 5], g[MAXN + 5];
struct ThreeMin {
int a, b, c;
void insert(int x) {
if (x < a) {
c = b;
b = a;
a = x;
} else if (x < b) {
c = b;
b = x;
} else if (x < c) {
c = x;
}
}
void erase(int x) {
if (x == b) {
b = c;
c = INF;
} else if (x == a) {
a = b;
b = c;
c = INF;
}
}
void init() {
a = b = c = INF;
}
ThreeMin() { init(); }
};
ThreeMin vf[MAXN + 5], vg[MAXN + 5];
void dfs3(int u) {
vf[u].init();
vg[u].init();
if (mark[u]) {
vf[u].insert(-bob_dis[u]);
if (bob_dis_from_fa[u] + 1 != bob_dis[u]) {
vg[u].insert(-bob_dis[u]);
}
}
for (int i = vir_head[u]; i; i = vir_edge[i].nxt) {
int v = vir_edge[i].to;
fw[v] = vir_edge[i].w;
dfs3(v);
if (f[v] != INF)
vf[u].insert(f[v] + vir_edge[i].w);
if (g[v] != INF)
vg[u].insert(g[v] + vir_edge[i].w);
}
f[u] = vf[u].a;
g[u] = vg[u].a;
}
void dfs4(int u, int fa) {
if (fa) {
int ff;
if (f[u] + fw[u] == vf[fa].a) {
ff = vf[fa].b;
} else {
ff = vf[fa].a;
}
if (ff != INF) {
vf[u].insert(ff + fw[u]);
}
f[u] = vf[u].a;
int gg;
if (g[u] + fw[u] == vg[fa].a) {
gg = vg[fa].b;
} else {
gg = vg[fa].a;
}
if (mark[fa] && flag[jump(u, fa)]) {
ckmin(gg, -bob_dis[fa]);
}
if (gg != INF) {
vg[u].insert(gg + fw[u]);
}
g[u] = vg[u].a;
}
if (mark[u] && bob_dis_from_fa[u] + 1 != bob_dis[u]) {
vg[u].erase(-bob_dis[u]);
}
for (int i = vir_head[u]; i; i = vir_edge[i].nxt) {
int v = vir_edge[i].to;
dfs4(v, u);
}
}
void solve(const vector<int>& q, int l, int r) {
// q 中这些询问的答案在 [l, r] 之间
if (!SZ(q))
return;
if (l == r || bob_dis[nodes_sorted_by_bob_dis[l]] == bob_dis[nodes_sorted_by_bob_dis[r]]) {
for (int i = 0; i < SZ(q); ++i) {
ans[q[i]] = l;
}
return;
}
int mid = (l + r) >> 1;
cnt = 0;
for (int i = 0; i < SZ(q); ++i) {
nodes_sorted_by_dfn[++cnt] = q[i];
}
for (int i = mid + 1; i <= r; ++i) {
nodes_sorted_by_dfn[++cnt] = nodes_sorted_by_bob_dis[i];
mark[nodes_sorted_by_bob_dis[i]] = 1;
}
sort(nodes_sorted_by_dfn + 1, nodes_sorted_by_dfn + cnt + 1, cmp_by_dfn);
cnt = unique(nodes_sorted_by_dfn + 1, nodes_sorted_by_dfn + cnt + 1) - (nodes_sorted_by_dfn + 1);
top = 0;
if (nodes_sorted_by_dfn[1] != 1)
add_node(1);
for (int i = 1; i <= cnt; ++i)
add_node(nodes_sorted_by_dfn[i]);
for (int i = 2; i <= top; ++i)
vir_add_edge(sta[i - 1], sta[i], dep[sta[i]] - dep[sta[i - 1]]);
dfs3(1);
dfs4(1, 0);
vir_tot = 0;
TIM++; // 懒惰清空
for (int i = mid + 1; i <= r; ++i) {
mark[nodes_sorted_by_bob_dis[i]] = 0;
}
vector<int> ql, qr;
for (int i = 0; i < SZ(q); ++i) {
if (f[q[i]] < 0 || (f[q[i]] == 0 && g[q[i]] == 0)) {
qr.pb(q[i]);
} else {
ql.pb(q[i]);
}
}
solve(ql, l, mid);
solve(qr, mid + 1, r);
}
int main() {
cin >> n;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
add_edge(u, v);
add_edge(v, u);
}
TreeChainPartition :: init();
cin >> K;
for (int i = 1; i <= K; ++i) {
cin >> a[i];
mark[a[i]] = 1;
}
dfs1(1, 0);
dfs2(1, 0);
bob_dis_from_fa[1] = INF;
// for (int i = 1; i <= n; ++i) cerr << bob_dis[i] << "
"[i == n];
for (int i = 1; i <= K; ++i) mark[a[i]] = 0;
vector<int> q;
for (int i = 1; i <= n; ++i) q.pb(i);
for (int i = 1; i <= n; ++i) nodes_sorted_by_bob_dis[i] = i;
sort(nodes_sorted_by_bob_dis + 1, nodes_sorted_by_bob_dis + n + 1, cmp_by_bob_dis);
solve(q, 1, n);
for (int i = 1; i <= n; ++i) {
cout << bob_dis[nodes_sorted_by_bob_dis[ans[i]]] << "
"[i == n];
}
return 0;
}