竞赛讨论区 > 个人认为最清晰的最后一题思路

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

头像
TOM_BOY
发布于 2022-01-23 23:56:52 APP内打开
赞 1 | 收藏 1 | 回复1 | 浏览414

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

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐