题解 CF1466D 【13th Labour of Heracles】

SSerxhs

2021-01-04 10:52:18

Solution

结论:同色边必连通 证明:若存在同色边形成连通块 $A$ 和 $B$ 且 $A$ 权值更大,则可以把 $B$ 的颜色改为与它旁边任何一个颜色。由于 $B$ 不对答案贡献显然答案不劣,由于每次修改至少减少一个连通块所以总能调整到不能再调整为止,即同色边均连通的状态。 于是题意转化为划分为 $k$ 个连通块使得每个连通块点权和最大,我们可以直接考虑每个点的贡献,显然每个点周围若有 $x$ 种颜色则贡献了 $x$ 次。 考虑树形 $dp$ 设 $f_{u,x}$ 表示考虑第 $u$ 个点及其连父边用了 $x$ 种颜色的答案,列出方程可以发现这和 $x$ 的唯一关系就是当 $x\leftarrow x+k$ 时 $ans\leftarrow ans+k*v_u$ 所以完全不需要做一个显式的树形 dp,直接按照 $val$ 降序做贡献就可以了。由于 $k\le d_u$,所以每个点可以做的贡献次数是度数次。 ```cpp #include <bits/stdc++.h> using namespace std; typedef unsigned int ui; typedef long long ll; typedef unsigned long long ull; const int N=1e6+2; struct Q { int w,rd; bool operator<(const Q &o) const {return w>o.w;} }; Q q[N]; ll ans; int n,c,i,t,m,x,y,j,k,la,s,p; inline void read(register int &x) { register int c=getchar(),fh=1; while ((c<48)||(c>57)) { if (c=='-') {c=getchar();fh=-1;break;} c=getchar(); } x=c^48;c=getchar(); while ((c>=48)&&(c<=57)) { x=x*10+(c^48); c=getchar(); } x*=fh; } int main() { read(t); while (t--) { read(n); ans=0; for (i=1;i<=n;i++) read(q[i].w),q[i].rd=-1,ans+=q[i].w; for (i=1;i<n;i++) read(x),read(y),++q[x].rd,++q[y].rd; sort(q+1,q+n+1);i=1;printf("%lld",ans); while (i<=n) { if (q[i].rd) --q[i].rd,ans+=q[i].w,printf(" %lld",ans); else ++i; }puts(""); } } ```