[DS记录]P4183 [USACO18JAN]Cow at Large P

· · 个人记录

题意 : 给出一棵树形迷宫,叶节点是出入口。

现在有一个人闯入了迷宫深处,如果他达到出口就可以逃离。

可以在出入口放置守卫,守卫的移动速度和闯入者相同,若闯入者和守卫相遇则被抓住。

守卫和闯入者在移动过程中均可以观察到对方的位置,而后决策。

对于闯入者可能的每个起点,问至少需要多少个守卫才能确保闯入者无法逃脱?

------------ 先来观察一下性质。为了方便,不妨将起点置为根。 首先,守卫的目标相当于封锁所有的叶节点,如果这一目的达到,接下来就是瓮中捉鳖。 其次,如果闯入者来到了某个没有守卫的子树,就可以一路向下到达叶节点。由于移动速度相同,守卫是追不上他的。 对于某个点,若某个叶节点到达该子树的距离,不超过根到该点的距离,则称为可以封锁。 若某个点可以封锁,则该点的子树也可以封锁。 我们在所有可封锁的点中,去掉有祖孙关系的点,留下尽量浅的点,剩余的点(称为“表面点”)的个数即为答案。 具体实现时,首先把叶节点入队进行`bfs`,得到每个点到最近叶节点的距离。 然后从根向下`dfs`,若该点已经被封锁,则不进入子树。 形式化地讲,设 $d[u]$ 为 $u$ 到最近叶节点的距离,则能被封锁的判据是 : $d[u]\leq dis(rt,u)

若对每个起点做一次贪心,复杂度是 O(n^2) 的,无法通过。

考虑使用点分树,每个点出发到达的联通块会被剖分成 O(\log n) 个部分,每个部分有一个必经点。

对于点分树上的某个分治块,可以视为有根子问题,求出深度 dep[u]。

某个从 u 而来的询问为 : 查询除去某棵子树的部分中,满足 d[v]\leq dep[v]+dep[u] 的“表面点”个数。

“表面点”可以转化为 : 若父亲合法,则儿子不贡献。

由于若父亲能贡献,儿子必然贡献,我们可以在父亲处扣除儿子的贡献。

设 r[u] 为 u 的儿子个数,则 u 的点权为 1-r[u]。不难发现,若选择一整个子树,贡献恰为 1。

(可以认为r[u]总是等于度数-1,然而根的r[u]应该恰好是度数,根贡献到自己只有叶节点,特判即可)

对前面的条件移项变为 d[v]-dep[v]\leq dep[u] ,这是个一维偏序,直接前缀和即可。

可以证明 d[v]-dep[v] 的极差是 O(分治块大小) 的,这样复杂度就是严格 O(n\log n)。

对于某个子树不贡献的要求,可以容斥掉。

具体实现中,由于不需要在线回答,可以直接点分治,细节见代码。

#include<algorithm>
#include<cstdio>
#include<queue>
#define MaxN 70500
using namespace std;
vector<int> g[MaxN];
int n,d[MaxN];
void bfs()
{
  static queue<int> q;
  for (int u=1;u<=n;u++){
    if (g[u].size()==1)
      {q.push(u);d[u]=0;}
    else d[u]=n;
  }
  while(!q.empty()){
    int u=q.front();q.pop();
    for (int i=0,v;i<g[u].size();i++)
      if (d[v=g[u][i]]>d[u]+1){
        d[v]=d[u]+1;
        q.push(v);
      }
  }
}
int siz[MaxN],mp[MaxN],st[MaxN],tn,
    vis[MaxN],ef;
void pfs(int u)
{
  vis[st[++tn]=u]=ef;
  mp[u]=siz[u]=1;
  for (int i=0,v;i<g[u].size();i++)
    if (vis[v=g[u][i]]<ef){
      pfs(v);
      siz[u]+=siz[v];
      mp[u]=max(mp[u],siz[v]);
    }
}
int grt(int u)
{
  tn=0;ef++;pfs(u);
  int rt=0;
  for (int i=1,u;i<=tn;i++){
    u=st[i];
    mp[u]=max(mp[u],tn-siz[u]);
    if (mp[u]<mp[rt])rt=u;
  }return rt;
}
int dis[MaxN],c[MaxN];
void dfs(int u)
{
  vis[st[++tn]=u]=ef;
  c[u]=d[u]-dis[u];
  for (int i=0,v;i<g[u].size();i++)
    if (vis[v=g[u][i]]<ef){
      dis[v]=dis[u]+1;
      dfs(v);
    }
}
#define INF 1000000000
int _o[MaxN<<1],*o=_o+MaxN,tl,tr;
void calc(int low)
{
  tl=c[st[tn]];tr=c[st[tn]];
  for (int i=low;i<tn;i++){
    tl=min(tl,c[st[i]]);
    tr=max(tr,c[st[i]]);
  }for (int i=tl-1;i<=tr;i++)o[i]=0;
  for (int i=low;i<=tn;i++)
    o[c[st[i]]]+=2-(int)g[st[i]].size();
  for (int i=tl;i<=tr;i++)o[i]+=o[i-1];
}
int qry(int x)
{return x<tl ? 0 : tr<x ? o[tr] : o[x];}
int ans[MaxN];
void solve(int u)
{
  vis[u]=INF;tn=0;ef++;
  for (int t=0,v;t<g[u].size();t++)
    if (vis[v=g[u][t]]<INF){
      int low=tn+1;
      dis[v]=1;dfs(v);calc(low);
      for (int i=low;i<=tn;i++)
        ans[st[i]]-=qry(dis[st[i]]);
    }
  dis[u]=0;c[u]=d[u];
  st[++tn]=u;calc(1);
  for (int i=1;i<=tn;i++)
    ans[st[i]]+=qry(dis[st[i]]);
  for (int t=0,v;t<g[u].size();t++)
    if (vis[v=g[u][t]]<INF)
      solve(grt(v));
}
int main()
{
  scanf("%d",&n);
  for (int i=1,f,t;i<n;i++){
    scanf("%d%d",&f,&t);
    g[f].push_back(t);
    g[t].push_back(f);
  }bfs();
  mp[0]=n+1;solve(grt(1));
  for (int i=1;i<=n;i++)
    printf("%d\n",ans[i]-(d[i]==0));
  return 0;
}