题解

题面描述

题目给出一棵含有 $n$ 个结点的树，根节点为 $1$。每个结点的权值定义为该结点到结点 $1$ 的边数。现在允许操作：选择一个非 $1$ 号结点，将以该结点为根的子树重新挂接到结点 $1$ 下。要求求出经过一次该操作后整棵树权值之和的最小值。

思路

本题的思路是：先利用深度优先搜索求出每个结点到根结点的距离（即深度）和每个结点的子树大小，然后计算初始的权值和 $S=\sum d$；对于每个非根结点 $v$，将以 $v$ 为根的子树挂接到 $1$ 号结点后，该子树所有结点的深度都会降低 $d[v]-1$，所以改善量为 $subtree\_size[v] \times (d[v]-1)$，最后取所有非根结点中最大的改善量，从 $S$ 中减去即可得到最小的权值和。

1. 原始权值和的计算：
   初始时，每个结点的权值等于其到根结点 $1$ 的距离。可以通过深度优先搜索（$DFS$）计算出所有结点的深度，累加即可得到原始权值和

   $$S=\sum_{u=1}^{n}{d[u]}.$$

2. 操作对权值和的影响分析：
   设选择了结点 $v$（$v\neq 1$），原来 $v$ 的深度为 $d[v]$，且以 $v$ 为根的子树中的结点数为 $subtree\_size[v]$。

   • 操作后，$v$ 直接挂接到 $1$ 下，新深度变为 $1$；而 $v$ 子树内任意结点 $u$ 的深度变为 $1 + (d[u] - d[v]).$
   • 因此，这部分结点权值减少了
     $(d[u] - (1 + d[u]-d[v])) = d[v]-1.$
   • 整个子树的权值和减少量为
     $\text{improvement}$ = $subtree\_size[v] \times (d[v]-1).$

3. 目标转换：
   为了使整体权值和最小，我们需要最大化提升量 $\text{improvement}$。因此，最终答案为
   $ans$ = $S$ - $max_{v\neq 1}${ $subtree\_size[v]$*$(d[v]-1)$ }.

$C++$ 解法

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int n; // n 表示树中结点的总数
vector<vector<int>> tree; // 存储树的邻接表
vector<int> depth; // 存储每个结点的深度
vector<int> subtree_size; // 存储每个结点的子树大小
ll total_depth = 0; // S，所有结点深度之和
ll best = 0; // 记录最大提升量

// 深度优先搜索函数
void dfs(int u, int parent, int d) {
    depth[u] = d; // 记录结点 u 的深度
    total_depth += d; // 累加到总权值和
    subtree_size[u] = 1; // 初始化子树大小（包含自身）
    for(auto v: tree[u]){
        if(v == parent) continue; // 避免回到父结点
        dfs(v, u, d+1); // 对子结点递归
        subtree_size[u] += subtree_size[v]; // 累加子树大小
    }
    if(u != 1){ // 只考虑非根结点
        ll improvement = (ll)subtree_size[u] * (d - 1);
        if(improvement > best) best = improvement; // 更新最大提升量
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    tree.resize(n+1);
    depth.resize(n+1,0);
    subtree_size.resize(n+1,0);
    // 读取边信息，构造树
    for(int i=1; i<=n-1; i++){
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    dfs(1, 0, 0); // 从结点 1 开始深搜，初始深度为 0
    cout << total_depth - best << "\n";
    return 0;
}

$Python$ 解法

def main():
    import sys
    sys.setrecursionlimit(300000)  # 增加递归深度限制
    n = int(sys.stdin.readline())
    tree = [[] for _ in range(n+1)]  # 构造邻接表
    for _ in range(n-1):
        u, v = map(int, sys.stdin.readline().split())
        tree[u].append(v)
        tree[v].append(u)
    
    depth = [0]*(n+1)         # 存储每个结点的深度
    subtree_size = [0]*(n+1)  # 存储每个结点的子树大小
    total_depth = 0         # 累加所有结点深度，表示 S
    best = 0                # 记录最大提升量

    # 深度优先搜索函数
    def dfs(u, parent, d):
        nonlocal total_depth, best
        depth[u] = d  # 记录结点 $u$ 的深度
        total_depth += d  # 累加到总权值和
        subtree_size[u] = 1  # 初始化子树大小
        for v in tree[u]:
            if v == parent:
                continue  # 避免回到父结点
            dfs(v, u, d+1)  # 对子结点递归
            subtree_size[u] += subtree_size[v]  # 累加子树大小
        if u != 1:  # 只考虑非根结点
            improvement = subtree_size[u] * (d - 1)  # 计算提升量
            best = max(best, improvement)  # 更新最大提升量

    dfs(1, 0, 0)  # 从结点 1 开始深搜，初始深度为 0
    print(total_depth - best)  # 输出结果

if __name__ == '__main__':
    main()

$Java$ 解法

import java.io.*;
import java.util.*;
public class Main {
    static int n; // n 表示树中结点的总数
    static ArrayList<ArrayList<Integer>> tree; // 存储树的邻接表
    static int[] depth; // 存储每个结点的深度
    static int[] subtreeSize; // 存储每个结点的子树大小
    static long totalDepth = 0; // S，所有结点深度之和
    static long best = 0; // 记录最大提升量

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine().trim());
        tree = new ArrayList<>();
        for(int i = 0; i <= n; i++){
            tree.add(new ArrayList<Integer>());
        }
        depth = new int[n+1];
        subtreeSize = new int[n+1];
        // 读取边信息，构造树
        for(int i = 1; i <= n-1; i++){
            String[] parts = br.readLine().split(" ");
            int u = Integer.parseInt(parts[0]);
            int v = Integer.parseInt(parts[1]);
            tree.get(u).add(v);
            tree.get(v).add(u);
        }
        dfs(1, 0, 0); // 从结点 1 开始深搜，初始深度为 0
        // 输出结果：totalDepth - best
        System.out.println(totalDepth - best);
    }
    
    // 深度优先搜索函数
    static void dfs(int u, int parent, int d) {
        depth[u] = d; // 记录结点 u 的深度
        totalDepth += d; // 累加到总权值和
        subtreeSize[u] = 1; // 初始化子树大小
        for(int v : tree.get(u)){
            if(v == parent) continue; // 避免回到父结点
            dfs(v, u, d+1); // 对子结点递归
            subtreeSize[u] += subtreeSize[v]; // 累加子树大小
        }
        if(u != 1){ // 只考虑非根结点
            long improvement = (long)subtreeSize[u] * (d - 1); // 计算提升量
            best = Math.max(best, improvement); // 更新最大提升量
        }
    }
}

题目内容

小红拿到一棵树，结点总数为$n$，根节点为$1$

定义每个点的权值为到结点$1$的边数。

现在小红可以选择一个非1号结点，使得以该结点为根节点的子树成为$1$号结点的子结点。

求整棵树的最小权值之和是多少?

输入描述

第一行一个整数$n(1≤n≤2×10^5)$,表示树的结点总数。

接下来$n-1$行，每行两个整数$u,v(1 ≤u,v≤n)$,表示$u$和$v$之间有一条边。

输出描述

一个整数，表示整棵树的最小权值之和。

样例1

输入

5
1 2
2 3
3 4
4 5

输出

6