D59 树的直径 树上前缀和 P4271 [USACO18FEB] New Barns P

D59 树的直径 树上前缀和 P4271 [USACO18FEB] New Barns P_哔哩哔哩_bilibili

 

P4271 [USACO18FEB] New Barns P - 洛谷

对空树做 m 次操作，支持两种操作：一种是对新建点连边，另一种是查询所给点到最远点的距离。

思路

对树有 加边、删边 操作，当然会想到 Link Cut Tree，参考 C07【模板】P3690 动态树（LCT） - 董晓 - 博客园

但是 LCT 的代码实现太复杂。

既然本题只有 加边 和 查询，我们考虑先离线建出整棵树，倍增维护 LCA，用树上前缀和计算两点间的距离。

• 性质1：一个点 u 在树内的最远点，一定是这棵树的直径的一个端点。
• 性质2：两棵树用一条边连起来的时候，新直径的端点一定是两棵树的直径端点之中的两个。

注意本题可能是一个森林，于是我们建一个超级源点 0 作为树根。

DFS一遍，预处理出 dep,fa,root 数组。用 root 数组记录每个点所在树（源点 0 下面挂着的子树）的树根节点。

我们枚举 m 次操作，

• 遇到连边，我们就更新当前树的直径端点，把两端点记录在所在树的根上。
• 遇到查询，我们就取出查询点所在树的树根，计算查询点到当前树的直径两端点的距离取最大。

      x=root[q[i]]; //取出新增点qi所在树的树根x，把新直径的两个端点记录在树根x上
      d=dis(point[x][0],point[x][1]); //求出当前树x的旧直径
      d0=dis(q[i],point[x][0]);       //求出qi到x的直径左端的距离
      d1=dis(q[i],point[x][1]);       //求出qi到x的直径右端的距离
      if(d==0) point[x][0]=q[i];      //如果旧直径为0，就让新直径左端点为qi
      else if(d0>d) point[x][1]=q[i]; //如果qi到左端点的距离更大，就让新直径右端点为qi
      else if(d1>d) point[x][0]=q[i]; //如果qi到右端点的距离更大，就让新直径左端点为qi

更新当前树的直径端点的代码，解释一下

如图，当我们插完节点 1，再插节点 2 时，因为 旧树只有一个点，直径两个端点都是 1，所以旧直径为 0，这时我们只需让直径的一个端点移到 2 上即可。

当我们插完 5 个节点，现在插节点 6 时，计算的旧直径一定是 3 到 5 之间的距离为 4，因为 6 到 5 的距离大于 4，所以把直径左端点从 3 移到 6。

                                     

// 树的直径 树上前缀和 O(nlogn)
#include<bits/stdc++.h>
using namespace std;

const int N=100010;
int h[N],idx,to[N],ne[N];
void add(int u,int v){
  to[++idx]=v;ne[idx]=h[u];h[u]=idx;
}
int n,m,opt[N],q[N],point[N][2];

int dep[N],fa[N][21],root[N];
void dfs(int u){
  for(int i=h[u]; i; i=ne[i]){
    int v=to[i];
    dep[v]=dep[u]+1; fa[v][0]=u;
    for(int i=1;i<=20;++i) fa[v][i]=fa[fa[v][i-1]][i-1];
    root[v]=u==0?v:root[u]; //记录v所在树的树根
    dfs(v);
  }
}
int lca(int u,int v){
  if(dep[u]<dep[v]) swap(u,v);
  for(int i=20;i>=0;--i)if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
  if(u==v) return u;
  for(int i=20;i>=0;--i)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
  return fa[u][0];
}
int dis(int u,int v){
  return dep[u]+dep[v]-2*dep[lca(u,v)];
}
int main(){
  scanf("%d",&m);
  for(int i=1,x; i<=m; ++i){
    char ch[2]; scanf("%s %d",ch,&x);
    opt[i]=(ch[0]=='B'?1:2);
    if(opt[i]==1) add(x==-1?0:x, q[i]=++n); //0是超级源点
    else q[i]=x;
  }
  dfs(0); //倍增预处理 dep,fa,root 数组
  for(int i=1; i<=n; ++i) point[i][0]=point[i][1]=i; //直径的两个端点初值重合
  
  for(int i=1,x,d,d0,d1; i<=m; ++i){
    if(opt[i]==1 && q[i]!=-1){
      x=root[q[i]]; //取出新增点qi所在树的树根x，把新直径的两个端点记录在树根x上
      d=dis(point[x][0],point[x][1]); //求出当前树x的旧直径
      d0=dis(q[i],point[x][0]);       //求出qi到x的直径左端的距离
      d1=dis(q[i],point[x][1]);       //求出qi到x的直径右端的距离
      if(d==0) point[x][0]=q[i];      //如果旧直径为0，就让新直径左端点为qi
      else if(d0>d) point[x][1]=q[i]; //如果qi到左端点的距离更大，就让新直径右端点为qi
      else if(d1>d) point[x][0]=q[i]; //如果qi到右端点的距离更大，就让新直径左端点为qi
    }
    if(opt[i]==2){
      x=root[q[i]]; //取出点qi所在树的树根x，计算点qi到当前树x的直径端点的最远距离
      printf("%d\n",max(dis(q[i],point[x][0]),dis(q[i],point[x][1])));
    }
  }
}