树论

· · 算法·理论

树的基本概念

1.树是无环图，自己的最小生成树。 \ 2.N个节点，N-1条边的联通无向图（无环），只有一条路。

有根树

1.存储

for(int i=1;i<=n;i++)
{
    cin>>x>>y>>z;
    e[x].push_back({y,z}）;
    e[y].push_back({x,z});
    fa[y]=x;//记录父亲节点
}

树的遍历

判断父亲结点：

1.使用vis数组

void dfs(int u)
{
    for(auto i:e[u)
    {
         int v=i.v,w=i.w;
         if(!vis[v])
         {
              vis{v]=1
              dfs(v)
         }
     }
}

2.父亲结点传入信息

基础模板


void dfs(int u,int fa)
{

    if(dis>d)
         return ;
    for(auto i:e[u])
    {
         int v=i.v,w=i.w;
         if(v==fa)
         {
               continue;
         }
         dfs(v,u);

     }
}

变形1


int size[N];//统计子树的结点个数
void dfs(int u,int fa)
{
    size[u]=1;//统计子树的结点个数
    if(dis>d)
         return ;
    for(auto i:e[u])
    {
         int v=i.v,w=i.w;
         if(v==fa)
         {
               continue;
         }
         dfs(v,u);
         size[u]+=size[v];//统计子树的结点个数
         abs(size[u]*2-n)*w;
     }

}//P2052 [NOI2011] 道路修建为例

变形2


int size[N];//统计子树的结点个数
void dfs(int u,int fa)
{
    size[u]=1;//统计子树的结点个数
    if(dis>d)
         return ;
    for(auto i:e[u])
    {
         int v=i.v,w=i.w;
         if(v==fa)
         {
               continue;
         }
         dfs(v,u);
         size[u]+=size[v];//统计子树的结点个数
         abs(size[u]*2-n)*w
     }
     if(size[u]==k)//判断结点数量是否为K
      {
            cnt++;
            size[u]=0;
      }

}//P3915 树的分解

遍历特点：边数 * 2=路径长度

树的重心

某个点被拿出后，原来的树会被分为子结点数+1（父亲结点以上） 棵树

定义：拿掉的一个点后能使所有分出的子树中的结点数最大的结点数最小，也就是最平均

特点

1.最多只有两个重心且两个重心相邻 \ 2.以重心为根的子树不超过原树的一半 \ 3.一个或两个重心到各个结点的距离和最小 \ 4.两棵树通过一条边相连，新树的重心在连接原来两棵树的重心的路径上

代码实现

int size[N],z1,z2;
void dfs(int u,int fa)
{
    size[u]=1;//统计子树的结点个数
    for(auto i:e[u])
    {
        int v=i.v,w=i.w;
        if(v==fa)
        {
              continue;
        }
        dfs(v,u); 
        size[u]+=size[v];//统计子树的结点个数
        w[u]=max(w[u],size[v]);//下方子树max 
    }
    w[u]=max(w[u],n-size[u]);//上方子树max 
    if(w[u]<=n/2)
     {
       if(z1)
       {
            z2=u;
       }
       else
       {
            z1=u;
       }
    } 
}

变形

int size[N],z1,z2;
void dfs(int u,int fa)
{
    size[u]=1;//统计子树的结点个数
    for(auto i:e[u])
    {
        int v=i.v,w=i.w;
        if(v==fa)
        {
              continue;
        }
        dfs(v,u); 
        size[u]+=size[v];//统计子树的结点个数
        w[u]=max(w[u],size[v]);//下方子树max 
    }
    w[u]=max(w[u],sum-size[u]);//上方子树max 
    if(w[u]<=sum/2)//点有权值
     {
       if(z1)
       {
            z2=u;
       }
       else
       {
            z1=u;
       }
    } 
}

树的重心的应用

1.

void dfs(int x,int f)
{
    size[x]=1;
    for(auto i:e[x])
    {
         if(i==1) continue;
         dfs(i,x);
         size[x]+=size[i];//不能放dfs前
         w=max(x,size[i]);
    }
    w=max(w,n-size[x]);
    if(w<=n/2)
    {
         x=
    }
}//适用于医院设置等问题

2.

int dis[N];
dis[st]=0;//st 为起点
void dfs(int x,int f)
{
    for(auto i:e[x])
    {
         int v=i.v,w=i.w;//i为结构体
         if(i==1) continue;
         dis[i]=dis[x]+w;
         ans=max(ans,dis[v]);//遍历用的是i的信息，否则层级会错乱
         dfs(i,x);
    }
}

树的直径

1.定义：树的两点之间最远的距离（不一定要过根节点）

2.求法

1.做两次dfs/bfs——边权都是非负值、代码简单

16:13

2.树形DP——任意边权值、代码难写

树的中心

1.定义：到其他所有点的最大距离最小的点（一定在树的直径上）

2.以树的中心为整棵树的根时，从根到叶子节点的最长路径最短（树最浅）

3.当树的边权为1时，树的中心一定为树的直径的中点