题解--重构
abruce
·
·
题解
10pts
你爆搜出这棵树应该都可以过。
30pts
由 prufer 序列我们得知，对于一个度数的序列 d，如果 \forall 1\le d_i<n,\sum d_i=2n-2。那么就一定可以生成至少一棵树。
所以我们只需要构造出合法的 d 序列，就可以求得最大值。
于是我们可以写出一个 O(n^3) 的 dp：设 f_{i,j} 为前 i 个点放了 j 的度数的最小代价。dp 转移方程：f_{i,j}=\min\limits_{k=i-1}^{j-1}f_{i-1,k}+(j-k)^2v_i。
50pts
对上面那个式子进行斜率优化。
100pts
首先我们对于每个点先放一个度数，消除 $\forall 1\le d_i<n,\sum d_i=2n-2$ 的限制。然后把 $((d_i+1)^2-d_i^2)v_i$ 当成费用丢进堆里，一直选，每一次将选出来的 $d_i$ 加 $1$，更新贡献，选 $n-1$ 次就可以。
一个口胡的证明：如果当前你选了一个更劣的解，它解锁出来的一定也是更劣的解，所以不如就选当前最优解。
代码很好实现。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+5;
struct que {
int w,v;
que(int W,int V) {
w=W,v=V;
}
friend bool operator<(que a,que b) {
return (2*a.w+1)*a.v>(2*b.w+1)*b.v;//按照增加的费用排序
}
};
int n,v[maxn];
ll ans;
priority_queue<que> q;
int main() {
scanf("%d",&n);
for(register int i=1; i<=n; i++)scanf("%d",&v[i]),ans+=v[i],q.push(que(1,v[i]));
for(register int i=1; i<n-1; i++) {
que u=q.top();
q.pop();
ans+=(2*u.w+1)*u.v;
if(u.w<n-1)q.push(que(u.w+1,u.v));
}
printf("%lld",ans);
return 0;
}
```