Codeforces Round #525 (Div. 2) E. Ehab and a component choosing problem 数学
题意：给出树 求最大的sigma(a)/k k是选取的联通快个数 联通快不相交
思路： 这题和1个序列求最大的连续a 的平均值 这里先要满足最大平均值 而首先要满足最大 也就是一个数的时候可以找出最大值
满足第二个条件最长 也就是看最大值有多少个连续即可
而本题 也就是先找出最大值然后看直接先求出最大的一个联通快的max(sigma(a)) 然后算一共有多少个联通快等于这个最大的sigma即可
一开始还当dp做其实是个***题。。
1 #include<bits/stdc++.h> 2 #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++) 3 #define MS(arr,arr_value) memset(arr,arr_value,sizeof(arr)) 4 #define F first 5 #define S second 6 #define pii pair<int ,int > 7 #define mkp make_pair 8 #define pb push_back 9 #define arr(zzz) array<ll,zzz> 10 using namespace std; 11 typedef long long ll; 12 const int maxn=3e5+5; 13 const int inf=0x3f3f3f3f; 14 int a[maxn]; 15 struct Node{ 16 int next,to; 17 }edge[maxn*2]; 18 int head[maxn]; 19 int size=0; 20 int n; 21 ll dp[maxn]; 22 void add(int x,int y){ 23 edge[size].to=y; 24 edge[size].next=head[x]; 25 head[x]=size++; 26 } 27 ll ans=-inf; 28 ll dfs(int now,int fa){ 29 ll sum=a[now]; 30 for(int i=head[now];i!=-1;i=edge[i].next){ 31 int to=edge[i].to; 32 if(to!=fa){ 33 sum=max(sum,sum+dfs(to,now)); 34 } 35 } 36 ans=max(ans,sum); 37 return sum; 38 } 39 ll cnt=0; 40 ll dfs2(int now,int fa){ 41 ll sum=a[now]; 42 for(int i=head[now];i!=-1;i=edge[i].next){ 43 int to=edge[i].to; 44 if(to!=fa){ 45 sum=max(sum,sum+dfs2(to,now)); 46 } 47 } 48 if(sum==ans)cnt++,sum=0; 49 return sum; 50 } 51 int main(){ 52 memset(head,-1,sizeof(head)); 53 scanf("%d",&n); 54 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 55 for(int i=1;i<n;i++){ 56 int x,y; 57 scanf("%d%d",&x,&y); 58 add(x,y); 59 add(y,x); 60 } 61 dfs(1,-1); 62 dfs2(1,-1); 63 cout<<ans*cnt<<" "<<cnt<<endl; 64 return 0; 65 }
