题解 CF1466D 【13th Labour of Heracles】
SSerxhs
2021-01-04 10:52:18
结论:同色边必连通
证明:若存在同色边形成连通块 $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("");
}
}
```