个人认为最清晰的最后一题思路

根据重心的定义：若以重心为根结点，则所有其每个子树的大小都不超过整棵树大小的一半 sum/2。

那么只需要将各个子树的大小总和sum和最大的子树max比较，

一种情况：如果最大子树max都小于sum的一半，那么每个子树上的结点都可以作为重心 cout<<sum

另一种情况：最大子树大小超过了sum的一半，那么重心只可能在结点max最大的子树上，且必然是中间部分。右因为一条链是对称的，所以只需要排除左边无效端点就可以知道 即重心=最大max-一端无效*2

如何求一端无效端点；

设一条链上的重点左边之和为x，右边结点之和为y。放缩到最长的无效点，因为从一端开始，所以只要右边y满足了<=sum/2就可。 即一端无效点=max-1-sum/2

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+100;
int a[N];
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n,sum=0,max=0;
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>a[i];sum+=a[i];max=(max,a[i]);
        }
        if(max<=sum/2) cout<<sum;
        else {//只跟最大的有关
            cout<<max-( max-1-sum/2)*2;
        }

        cout <<endl;
    }

}