树的直径与重心

• 重心
• 直径

树的重心

定义：
树上一节点，它最大子树的节点数最小，有时定义为其最大子树权值
讨论其在节点的数定义下的
性质：
1. 删除重心之后得到的所有子树中，节点数不超过原来节点数的1/2,
2.一棵树最多有两个重心
3.树中的所有节点到重心的距离之和最小
4.树删除或者添加一个叶子节点，重心最多只移动一条边
5.两棵树通过一条边合并，新的重心会在原来两个重心的路径上

求解：

方法一：

dfs搜索时dp维护每一个节点作为根节点时的最大子树节点数

int size[N];
int fa[N];
int dp[N];
void dfs(int x){
  size[x]=1;
  dp[x]=0;
  int k=head[x];
  while(k){
    if(e[k].to!=fa[x]){
      fa[e[k].to]=x;
      dfs(e[k].to);
      size[x]+=size[e[k].to];
      dp[x]=max(dp[x],size[e[k].to]);
    }
    k=e[k].next;
  }
  dp[x]=max(dp[x],n-size[x]);
  if(dp[x]<dp[ans]) ans=x;
  return ;
}

方法二:

两次dfs，第一次预处理出每个节点到自定义根节点的距离总和，各节点的父亲。第二次dfs动规求解出每一个节点作为根节点时，其他节点到它的距离总和
转移方程:
$\qquad dp[v]=dp[u]-size[v]+size[1]-dp[v]$
$\qquad dp[v]=dp[u]+size[1]-2*size[v]$

int deep[N];
int size[N];
int fa[N];
int dp[N];
void dfs1(int x){
  cout<<x<<'*'<<endl;
  size[x]=1;
  deep[x]=deep[fa[x]]+1;
  int k=head[x];
  while(k){
    if(e[k].to!=fa[x]){
      fa[e[k].to]=x;
      dfs1(e[k].to);
      size[x]+=size[e[k].to];
      dp[x]=dp[e[k].to]+size[e[k].to];
    }
    k=e[k].next;
  }
}
void dfs2(int x){
  int k=head[x];
  while(k){
    if(e[k].to!=fa[x]){
      dp[e[k].to]=dp[x]-size[e[k].to]+size[1]-size[e[k].to];
      if(dp[ans]>dp[e[k].to]) ans=e[k].to;
      dfs2(e[k].to);
    }
    k=e[k].next;
  }
}

可以发现，重心只会出现在最大的子树中，记录每一个节点的“重儿子”，只搜索重边，对随机数据十分有用

int son[N];
int dp[N];
int fa[N];
int deep[N];
int size[N];
void dfs1(int x){
  size[x]=1;
  deep[x]=deep[fa[x]]+1;
  int k=head[x];
  while(k){
    if(e[k].to!=fa[x]){
      fa[e[k].to]=x;
      dfs1(e[k].to);
      size[x]+=size[e[k].to];
      dp[x]+=dp[e[k].to]+size[e[k].to];
      if(size[son[x]]<size[e[k].to]) son[x]=e[k].to;
    }
    k=e[k].next;
  }
}
void dfs2(int x){
  if(!son[x]) return ;
  dp[son[x]]=dp[x]+size[1]-2*size[son[x]];
  if(dp[ans]>dp[son[x]]) ans=son[x];
  dfs2(son[x]);
}

例题：树的双中心

考虑暴力删边操作，将树分成两个部分，求两棵树的重心。枚举出使得答案最小的两个重心即可
注意状态转移方程和一些小细节

#include<iostream>
#include<cmath>
#include<cstdio>
#define ll long long
#define N 500010
const int inf=2147483600;
using namespace std;
int n;
int val[N];
int tot_ans=inf;
struct node{
  int to;
  int next;
}e[2*N];
int arr;
int head[N];
void add(int u,int v){
  e[++arr].next=head[u];
  e[arr].to=v;
  head[u]=arr;
}
int deep[N];
int size[N];
int son1[N];
int son2[N];
int fa[N];
int f[N];
void dfs(int x){
  deep[x]=deep[fa[x]]+1;
  size[x]=val[x];
  int k=head[x];
  while(k){
    if(e[k].to!=fa[x]){
      fa[e[k].to]=x;
      dfs(e[k].to);
      size[x]+=size[e[k].to];
      f[x]+=f[e[k].to]+size[e[k].to];
      if(size[son1[x]]<size[e[k].to]){
        son2[x]=son1[x];
        son1[x]=e[k].to;
      }else{
        if(size[son2[x]]<size[e[k].to]){
          son2[x]=e[k].to;
        }
      }
    }
    k=e[k].next;
  }
}
int shan;
void get_ans(int x,int now,int top,int &ans){
  ans=min(ans,now);
  int v=son1[x];
  if(size[son1[x]]<size[son2[x]]||v==shan){ v=son2[x]; }
  if(size[v]*2>top&&v){ get_ans(v,now+top-2*size[v],top,ans); }
  return ;
}
void era(int x){
  int k=head[x];
  while(k){
    if(e[k].to!=fa[x]){
      shan=e[k].to;
      int i=x;
      while(i){
        size[i]-=size[e[k].to];
        i=fa[i];
      }
      int a=inf;
      int b=inf;
      get_ans(1,f[1]-f[e[k].to]-(deep[e[k].to]-deep[1])*size[e[k].to],size[1],a);
      get_ans(e[k].to,f[e[k].to],size[e[k].to],b);
      tot_ans=min(tot_ans,a+b);
      i=x;
      while(i){
        size[i]+=size[e[k].to];
        i=fa[i];
      }
      era(e[k].to);
    }
    k=e[k].next;
  }
}
int main()
{
  scanf("%d",&n);
  for(int i=1;i<n;++i){
    int u,v;
    scanf("%d%d",&u,&v);
    add(u,v); add(v,u);
  }
  for(int i=1;i<=n;++i){
    scanf("%d",&val[i]);
  }
  dfs(1);
  era(1);
  cout<<tot_ans<<endl;
  return 0;
}