题意（考试时看错了对着样例wa了好久..）：从树上选k个连通块，使得权值的平均值最大的基础上，选的块数最多
如果不考虑块数最多的限制，肯定是只选一个权值最大的块是最好的
然后只要看这个权值最大的块有多少个不相交的就可以了
做法就是，在dp的时候，一旦找到了和最大权值相等的块，直接统计答案，然后把这一块的权值改成-inf
1 #include<bits/stdc++.h> 2 #define pa pair<int,int> 3 #define CLR(a,x) memset(a,x,sizeof(a)) 4 #define MP make_pair 5 using namespace std; 6 typedef long long ll; 7 const int maxn=3e5+10; 8 9 inline char gc(){ 10 return getchar(); 11 static const int maxs=1<<16;static char buf[maxs],*p1=buf,*p2=buf; 12 return p1==p2&&(p2=(p1=buf)+fread(buf,1,maxs,stdin),p1==p2)?EOF:*p1++; 13 } 14 inline ll rd(){ 15 ll x=0;char c=gc();bool neg=0; 16 while(c<'0'||c>'9'){if(c=='-') neg=1;c=gc();} 17 while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0',c=gc(); 18 return neg?(~x+1):x; 19 } 20 21 int N,a[maxn]; 22 int eg[maxn*2][2],egh[maxn],ect; 23 ll f[maxn],answ=-1e15,ansk; 24 25 inline void adeg(int a,int b){ 26 eg[++ect][0]=b,eg[ect][1]=egh[a],egh[a]=ect; 27 } 28 29 inline void dfs1(int x,int fa){ 30 f[x]=a[x]; 31 for(int i=egh[x];i;i=eg[i][1]){ 32 int b=eg[i][0];if(b==fa) continue; 33 dfs1(b,x); 34 if(f[b]>0) f[x]+=f[b]; 35 } 36 answ=max(answ,f[x]); 37 } 38 inline void dfs2(int x,int fa){ 39 f[x]=a[x]; 40 for(int i=egh[x];i;i=eg[i][1]){ 41 int b=eg[i][0];if(b==fa) continue; 42 dfs2(b,x); 43 if(f[b]>0) f[x]+=f[b]; 44 } 45 if(f[x]==answ) ansk++,f[x]=-1e15; 46 } 47 48 int main(){ 49 //freopen("","r",stdin); 50 int i,j,k; 51 N=rd(); 52 for(i=1;i<=N;i++) a[i]=rd(); 53 for(i=1;i<N;i++){ 54 int a=rd(),b=rd(); 55 adeg(a,b);adeg(b,a); 56 } 57 dfs1(1,0);dfs2(1,0); 58 answ*=ansk; 59 printf("%I64d %I64d ",answ,ansk); 60 return 0; 61 }