You are given a weighted tree consisting of 𝑛 vertices. Recall that a tree is a connected graph without cycles. Vertices 𝑢𝑖 and 𝑣𝑖 are connected by an edge with weight 𝑤𝑖.

Let's define the 𝑘-coloring of the tree as an assignment of exactly 𝑘 colors to each vertex, so that each color is used no more than two times. You can assume that you have infinitely many colors available. We say that an edge is saturated in the given 𝑘-coloring if its endpoints share at least one color (i.e. there exists a color that is assigned to both endpoints).

Let's also define the value of a 𝑘-coloring as the sum of weights of saturated edges.

Please calculate the maximum possible value of a 𝑘-coloring of the given tree.

You have to answer 𝑞 independent queries.

#### 链接🔗

「CodeForces 1241E」Paint the Tree

#### 题解

DP[x][1] 表示该点边选满了的价值
DP[x][0] 表示未选满的价值

#### 代码

const int maxd = 5e5+10;
typedef long long ll;

vector<P> G[maxd];
vector<ll> a;
ll n,k,dp[maxd][2];
// dp[i][0] 表示选满k边的最大价值
void dfs(ll x,ll fa)
{
//    PLL(x);
//    PN();
dp[x][0] = dp[x][1] = 0;
for(auto p:G[x])
{
ll v = p.st;
if(v == fa) continue;
dfs(v,x);
dp[x][0] += dp[v][1];
dp[x][1] += dp[v][1]; //先选满的子树
}
//选满的子树，这样当前节点就无法与子树节点连边，因为子树点已经满K个了

a.clear();
for(auto p:G[x])
{
ll v = p.st;
if(v == fa) continue;
a.pb(-(dp[v][0]+ p.nd - dp[v][1]));
//这里我们枚举每个节点的差值，也就是如果子树不选满，则可选这条边
}
sort(all(a)); //贪心选择价格高的

ll len = min((ll)a.size(),k);
F(len)
{
ll v = -a[i];
if(v < 0)break;
if(i<k-1) dp[x][0] += v;
dp[x][1] += v;
}
}

int main()
{
//    freopen("a.in","r",stdin);
//    freopen("k.out","w",stdout);
int t;scanf("%d",&t);
while(t--)
{
RLL(n);RLL(k);
F(n-1)
{
ll a,b,c;
RLL(a);RLL(b);RLL(c);
//printf("%lld %lld %lld\n",a,b,c);
G[a].pb(P(b,c));
G[b].pb(P(a,c));
}
//        FOR(1,n)
//        {
//            for(auto p: G[i]) printf("%lld ",p.st);
//            PN();
//        }
dfs(1ll,-1ll);
FOR(1,n) G[i].clear();
PLL(max(dp[1][0],dp[1][1]));
PN();

}

return 0;
}