根据重心的定义:若以重心为根结点,则所有其每个子树的大小都不超过整棵树大小的一半 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; } }
全部评论
(1) 回帖