题意分析

给定一个由(N)个谷仓构成的树状网络，需要找出切断哪些谷仓的连接后，网络分割成的各个部分所包含的谷仓数量都不超过谷仓总数的一半。

解题思路

利用深度优先搜索（DFS）遍历树，计算移除每个节点后，其各个子树的节点数量以及剩余部分的节点数量，找出满足条件的节点。

分析

- 对于树中的每个节点，移除它后，树会被分割成若干子树和剩余部分。

- 通过 DFS 可以计算出以每个节点为根的子树的节点数量。

- 对于每个节点，比较其各个子树的节点数量以及移除该节点后剩余部分的节点数量与谷仓总数一半的大小关系。

实现步骤

- 读取谷仓数量\(N\)和谷仓间的连接信息，构建图的邻接表表示。

- 从任意一个节点（这里选择节点 1）开始进行深度优先搜索。

- 在 DFS 过程中，计算以当前节点为根的子树的节点数量，记录其最大子树的节点数量。

- 计算移除当前节点后剩余部分的节点数量，取两者中的最大值作为该节点的\(dp\)值。

- 遍历所有节点，判断其\(dp\)值是否不超过谷仓总数的一半，若是则输出该节点编号。

- 如果没有满足条件的节点，输出“NONE”。

代码实现

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 5;
int n, dp[maxn], x, y;
vector<int> v[maxn];
bool vis[maxn];

int dfs(int p) {
    vis[p] = true;
    dp[p] = -1;
    int sum = 1, tmp, mson = -1;
    for(int i = 0; i < (int)v[p].size(); ++i) {
        int np = v[p][i];
        if(!vis[np]) {
            tmp = dfs(np);
            mson = max(tmp, mson); // 孩子中节点最多的那个
            sum += tmp;
            vis[np] = true;
        }
    }
    dp[p] = max(n - sum, mson);
    return sum;
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n - 1; ++i) {
        scanf("%d%d", &x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1);
    bool flag = false;
    for(int i = 1; i <= n; ++i) {
        if(dp[i] * 2 <= n) {
            flag = true;
            printf("%d\n", i);
        }
    }
    if(!flag) {
        printf("NONE\n");
    }
    return 0;
}

代码说明

- `dp[i]` 数组用于记录移除节点\(i\)后，分割出的最大部分的节点数量。

- `v[i]` 是一个向量数组，用于存储与节点\(i\)相连的节点，实现图的邻接表表示。

- `vis[i]` 数组用于标记节点是否被访问过，避免重复访问。

- `dfs` 函数用于进行深度优先搜索，计算以当前节点为根的子树的节点数量，并更新\(dp\)值。

- 在主函数中，读取输入数据，调用 `dfs` 函数进行搜索，然后遍历所有节点，输出满足条件的节点编号。