题解：CF1452G Game On Tree

· · 题解

Solution

记录我思考的过程，。

先考虑 Bob 的策略。显然，他只会让自己的卡片朝向 Alice 的卡片移动，而且一定会这么做。

Alice 的策略为：选定一条链 u \to v，将卡片放在 u 上。先不断向 v 移动。到达 v 之后，她会选择停在 v 不动，等着 Bob 来。

这样需要满足：

  1. 对于链上任何一点 w 和任何一个 Bob 起始点 s，都有 \text{dis}(u,w) < \text{dis}(s,w)；
  2. 最大化 \min_i \text{dis}(s_i,v)。

显然对于每个 v，都可以算出 t_v=\min_{i} \text{dis}(s_i,v) 的值。

那么问题转化为：给定 u，找到满足下列要求的 v 对应的 t_v 的最大值——u 到 v 路径上所有点 p 的 t_p 都大于 \text{dis}(u,p)。

关键性质：下面证明，路径 (u,v) 上任何一个点 p 满足 t_p > \text{dis}(u,p)，等价于 t_v > \text{dis}(u,v)。其实是显然的，因为我们将 p 从 u 往 v 移动时，t_v 最多增加 1，而 \text{dis}(u,v) 会减少 1，即 t_v - \text{dis}(u,v) 在减小。这样已经可以用一些分块乱做了，能做到 O(n \sqrt{n \log n})，不清楚能不能过。

大规模点对统计考虑点分治。每个点显然会对 dep_u \le k 的所有点产生贡献（不在同一子树内毫无影响，这样会更劣）。直接前缀和即可，复杂度 O(n \log n)。

这是代码：

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10;
int n,k,flg[MAXN],t[MAXN],ans[MAXN],din[MAXN],dout[MAXN],pre[MAXN];
vector<int> G[MAXN];
void dfs1(int u,int f) {for(auto v:G[u]) if(v!=f) dfs1(v,u),din[u]=min(din[u],din[v]+1);return ;}
void dfs2(int u,int f) {for(auto v:G[u]) if(v!=f) dout[v]=min(din[u],dout[u])+1,dfs2(v,u);return ;}
int cut[MAXN],dep[MAXN],sze[MAXN],mx[MAXN],mdep;
void dfs(int u,int f) {
    sze[u]=1,mx[u]=0;
    for(auto v:G[u]) if(v!=f&&!cut[v]) dfs(v,u),sze[u]+=sze[v],mx[u]=max(mx[u],sze[v]);
    return ;    
}
int find_core(int u,int f,int al) {
    if(max(mx[u],al-sze[u])<=al/2) return u;
    for(auto v:G[u]) if(v!=f&&!cut[v]) {
        int ans=find_core(v,u,al);
        if(ans!=-1) return ans;
    }
    return -1;
}
void get_dep(int u,int f,int& md) {
    if(f) dep[u]=dep[f]+1;
    else dep[u]=0;
    md=max(md,dep[u]+1);
    for(auto v:G[u]) if(v!=f&&!cut[v]) get_dep(v,u,md);
    return ;    
}
void add_imp(int u,int f) {
    if(t[u]-dep[u]-1>=0) pre[min(mdep,t[u]-dep[u]-1)]=max(pre[min(mdep,t[u]-dep[u]-1)],t[u]);
    for(auto v:G[u]) if(v!=f&&!cut[v]) add_imp(v,u);
    return ;
}
void add_ans(int u,int f) {
    ans[u]=max(ans[u],pre[dep[u]]);
    for(auto v:G[u]) if(v!=f&&!cut[v]) add_ans(v,u);
    return ;    
}
void solve(int u) {
    dfs(u,0),u=find_core(u,0,sze[u]);
    mdep=0,get_dep(u,0,mdep);
    ffor(i,0,mdep) pre[i]=-0x3f3f3f3f3f3f3f3f;
    add_imp(u,0);roff(i,mdep-1,0) pre[i]=max(pre[i],pre[i+1]);add_ans(u,0);
    cut[u]=1;for(auto v:G[u]) if(!cut[v]) solve(v);
    return ;
}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    ffor(i,1,n-1) {int u,v;cin>>u>>v,G[u].push_back(v),G[v].push_back(u);}
    cin>>k;
    memset(din,0x3f,sizeof(din)),memset(dout,0x3f,sizeof(dout));
    ffor(i,1,k) {int id;cin>>id,flg[id]=1,din[id]=dout[id]=0;}
    dfs1(1,0),dfs2(1,0);
    ffor(i,1,n) t[i]=min(din[i],dout[i]);
    solve(1);
    ffor(i,1,n) cout<<ans[i]<<' ';
    return 0;
}