小O的叶子

[题目链接](https://www.nowcoder.com/practice/e0b315f386354e0fbcfd4f69ece56a3a)

思路

给定一棵 个节点的树，枚举删除每个节点后，统计剩余森林中叶子节点（度恰好为 1 的节点）的数量，取最大值。

关键观察

暴力枚举每个节点并重新统计叶子数是 的。注意到树的边数为 ，度数之和为 ，可以用差量法将整体复杂度压到 。

设原树中叶子节点数为 （度为 1 的节点数），现在枚举删除节点 ：

1. 自身的影响：若 ，则 本身是叶子，删除后少一个叶子，。

1. 的邻居的影响：删除 后， 的每个邻居 的度减少 1，即 ：

- 若 ： 原来是叶子，删除后变为孤立节点（度为 0），不再是叶子，。

- 若 ： 原来不是叶子，删除后变为叶子（度为 1），。

- 若 ：删除后度仍 ，不是叶子，无影响。

对每个 计算调整后的叶子数，取最大值即为答案。

复杂度

由于每条边只被两个端点各处理一次，枚举所有 时对邻居遍历的总操作数为 ，所以整体时间复杂度为 ，空间复杂度 。

特殊情况

• ：删除唯一节点后为空树，叶子数为 0。
• ：删除任意节点后剩一个孤立节点（度为 0），叶子数为 0。

样例演示

，星形图，节点 1 连接 2、3、4、5：

• 原始叶子数 （节点 2、3、4、5 度均为 1）。
• 删除节点 5：，；邻居为节点 1，，无影响。结果为 3。
• 删除节点 1：，不调整；邻居 2、3、4、5 均度为 1，各 ，共 。结果为 。
• 最大值为 3，与样例一致。

代码

C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    if(n <= 2){
        printf("0\n");
        return 0;
    }
    vector<int> deg(n+1, 0);
    vector<vector<int>> adj(n+1);
    for(int i = 0; i < n-1; i++){
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }

    int L = 0;
    for(int i = 1; i <= n; i++){
        if(deg[i] == 1) L++;
    }

    int ans = 0;
    for(int v = 1; v <= n; v++){
        int res = L;
        if(deg[v] == 1) res--;

        for(int u : adj[v]){
            if(deg[u] == 1) res--;
            else if(deg[u] == 2) res++;
        }
        ans = max(ans, res);
    }

    printf("%d\n", ans);
    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        if (n <= 2) {
            System.out.println(0);
            return;
        }
        int[] deg = new int[n + 1];
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        for (int i = 0; i < n - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            adj.get(u).add(v);
            adj.get(v).add(u);
            deg[u]++;
            deg[v]++;
        }

        int L = 0;
        for (int i = 1; i <= n; i++) {
            if (deg[i] == 1) L++;
        }

        int ans = 0;
        for (int v = 1; v <= n; v++) {
            int res = L;
            if (deg[v] == 1) res--;
            for (int u : adj.get(v)) {
                if (deg[u] == 1) res--;
                else if (deg[u] == 2) res++;
            }
            ans = Math.max(ans, res);
        }
        System.out.println(ans);
    }
}