幽暗统领 树的重心 牛客白月赛44

幽暗统领 树的重心 牛客白月赛44

链接：https://ac.nowcoder.com/acm/contest/11221/F
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
黑云聚，妖风旋，幽暗统领法无边。

你获得了 nn 条链，第 ii 条链的长度是 a_ia
i
​
。

定义一条链的长度 lenlen：这条链是一个所有结点度数不超过 22，且包含恰好 lenlen 个结点的树。

接下来，你需要选定一种方案，给这 sum a_i∑a
i
​
个点再连上 n-1n−1 条边（前提是原来两个点在不同的联通块内），容易观察到这会使得它们构成一个包含 sum a_i∑a
i
​
个结点的“大树”。

请输出最终 可能 成为“大树”重心的结点的个数。 定义“可能”：在所有可能的连边方案中，只要存在一种方案，使得这个点就是最后“大树”的重心，那么就是有“可能”的。
输入描述:
全文第一行输入一个正整数 T(1le Tle10^5)T(1≤T≤10
5
)。

每组数据第一行输入一个正整数 n(1le nle10^5)n(1≤n≤10
5
)，表示链的个数。

第二行输入 nn 个正整数 a_i(1le a_ile10^9)a
i
​
(1≤a
i
​
≤10
9
)。

数据保证 sum nle3times10^6∑n≤3×10
6
。
输出描述:
每行输出一个整数，表示最终 可能 成为“大树”重心的结点的个数。
示例1
输入
复制
3
5
2 2 2 2 2
3
1 1 5
2
9 9
输出
复制
10
3
18
说明
对于样例 #1，很明显每个点都有可能成为重心，因为它们的地位本质上没有区别。

对于样例 #2，前两条链都是单点显然不会是重心，而第 33 个链的两端端点不可能是重心，所以总个数为 5-2=35−2=3 个。

对于样例 #3，显然每一个结点都可以是重心。

思路 ：

树的重心 ： 树的某个节点，去掉该节点后，树的各个连通分量中，结点数最多的连通分量的节点数最小

#include 
#include 
using namespace std;

typedef long long ll;

int main()
{
    int _; cin >> _;
    while (_ -- )
    {
        int n; cin >> n;
        
        ll mx = 0, sum = 0;
        for (int i = 0; i < n; i ++ )
        {
            ll x; cin >> x;
            mx = max(mx, x);
            sum += x;
        }
        
        ll remain = sum - mx;
        if (remain >= mx) cout << sum << endl;
        else
        {
            ll l = (sum + 1) / 2 - remain;
            ll r = mx - l + 1;
            cout << r - l + 1 << endl;
        }
    }
}