题解 P5666 【树的重心】

· · 题解

[CSP2019] 树的重心

题意

设 $E$ 为树的边集, $V'_x,\ V'_y$ 分别为删去边 $(x,y)$ 后 点 $x$ 所在的点集和点 $y$ 所在的点集. 求 $$ \sum_{(x,y) \in E} \left( \sum_{x \in V'_x} [x 是 V'_x 的重心] * x + \sum_{y \in V'_y} [y 是 V'_y 的重心] * y \right) $$ ## 思路 ### 40 pts 暴力枚举每一条边, 求重心即可. ### 100 pts #### 做法 1 总的思路是从枚举边变为枚举点, 具体操作 : 枚举每一个点 $u$, 对该点的每一棵子树都处理出 $w_i$ 表示, 该子树内权值为 $i$ 的边的个数, 这里边的权值定义为 : 以 $u$ 为根节点时, 删去这条边后, 删掉的节点个数. 再分类讨论当前枚举到的子树是不是权值最大的子树, 找到一个区间 $[l,r]$, 使删去的边的权值 $e_i \in [l,r]$ 时, 点 $u$ 为新树的重心, 用树状数组区间求和即可. 问题在于, 我们每次要独立地获得每个子树的边的数量, 所以就要用到线段树合并或者主席树, 不然的话每次重新获取子树的边的复杂度会达到 $O(n^2)$, 然后本人线段树合并与主席树都不会, 所以.... #### 做法 2 **总思路**: 利用倍增优化找重心的过程. **突破口**: 树的重心一定在根节点的重路径上. **证明**: 定义 $son[u]$ 为节点 $u$ 的重儿子. 设该树的根节点为 $t$, $v,\ u$ 为该树上的两个节点, 且 $fa[v]=u$, $v \not = son[u]$. **反证法**: 假设 $v$ 为以 $t$ 为根节点的树重心, 则 $ sz[t]-sz[v] \le \frac{sz[t]}{2} $, 所以 $ sz[v] \ge \frac{sz[t]}{2} $. 设 $p$, 满足 $fa[p]=u$, 且 $p \not = v$, 则 $sz[p] \le sz[u]-1-sz[v] \le sz[u]-1-\frac{sz[t]}{2} \le sz[t]-1-\frac{sz[t]}{2} \le sz[v]

所以 v 为 u 的重儿子, 产生矛盾, 假设不成立, 得证.

具体做法: 设 s[u][i] 为从节点 u 沿着重路径往下跳 2^i 步后到达的点. 设 t 为当前树的根节点. 当 sz[s[u][i]] > \frac{sz[t]}{2} 时, u=s[u][i], 不断往下跳, 直到找到第一个有可能成为重心的点, 然后判断这个点以及它的重儿子是不是重心 (因为一棵树最多只能由两个重心, 所以只需判断这两个点), 若是, 则加入答案中.

首先, 我们随便找一个点作为根节点, 那么这里我们默认选择 1 号点. 然后, 对于每一个节点, 我们枚举它连向子节点的每一条边, 然后分类讨论, 重新选择 u 的重儿子 (详见代码).

总时间复杂度 O(n\log n)

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=299995+7;
const int L=20;
int T,n,sz[N],son[N][2],s[N][L+7];
ll ans;
int lst[N],nxt[2*N],to[2*N],tot;
void add(int x,int y){ nxt[++tot]=lst[x]; to[tot]=y; lst[x]=tot; }
void rfs(int u){
  s[u][0]=son[u][0];
  for(int i=1;i<=L;i++)
    s[u][i]=s[s[u][i-1]][i-1];
}
void pre(int u,int fa){
  for(int i=lst[u];i;i=nxt[i]){
    int v=to[i];
    if(v==fa) continue;
    pre(v,u);
    sz[u]+=sz[v];
    if(sz[v]>sz[son[u][0]]){ son[u][1]=son[u][0]; son[u][0]=v; }
    else if(sz[v]>sz[son[u][1]]) son[u][1]=v;
  }
  sz[u]++;
  rfs(u);
}
void find(int u){
  int t=u;
  for(int i=L;i>=0;i--)
    if(sz[s[u][i]]>sz[t]/2)
      u=s[u][i];
  if(sz[t]-sz[u]<=sz[t]/2) ans+=(ll)u;
  u=s[u][0];
  if(sz[t]-sz[u]<=sz[t]/2) ans+=(ll)u;
}
void run(int u,int fa){
  int t1=son[u][0],t2=sz[u];        // 先备份
  for(int i=lst[u];i;i=nxt[i]){
    int v=to[i];
    if(v==fa) continue;
    if(v==t1) son[u][0]= sz[son[u][1]]>n-t2 ?son[u][1] :fa;        // 重新选取 u 的重儿子.
    else son[u][0]= sz[t1]>n-t2 ?t1 :fa;
    sz[u]=n-sz[v];
    rfs(u);    // 记得把 son[u][i] 也更新一遍
    find(u); find(v);
    run(v,u);
  }
  son[u][0]=t1;    // 还原
  sz[u]=t2;
  rfs(u);    //更新
}
int main(){
  //  freopen("gc.in","r",stdin);
  cin>>T;
  while(T--){
    scanf("%d",&n);
    memset(lst,0,sizeof(lst));
    memset(son,0,sizeof(son));
    memset(sz,0,sizeof(sz));
    tot=ans=0;
    int x,y;
    for(int i=1;i<n;i++){
      scanf("%d%d",&x,&y);
      add(x,y); add(y,x);
    }
    pre(1,0);
    run(1,0);
    printf("%lld\n",ans);
  }
  return 0;
}