Preparing NOJ

最大权边独立集

2000ms 524288K

Description:

给定一张 $$$n$$$ 个点 $$$n-1$$$ 条边的连通无向图,点的编号依次为 $$$1$$$ 到 $$$n$$$,第 $$$i$$$ 条边的边权为 $$$w_i$$$。

请往图中添加恰好 $$$k$$$ 条边权为 $$$p$$$ 的边,使得最大权边独立集的边权和最大,即在新图中找到一系列不含公共端点的边,使得这些边的边权和最大。注意:添加的边必须连接两个不同的点,但是两个点之间允许存在多条边。

Input:

第一行包含三个整数 $$$n,k,p$$$ ($$$2\leq n\leq 100\,000$$$, $$$0\leq k\leq 100$$$, $$$1\leq p\leq 10^9$$$),表示点数、要添加的边数以及要添加的边的权值。

接下来 $$$n-1$$$ 行,第$$$i$$$行包含三个正整数 $$$u_i,v_i,w_i$$$ ($$$1\leq u_i,v_i\leq n$$$, $$$1\leq w_i\leq 10^9$$$),表示第 $$$i$$$ 条边的端点是 $$$u_i$$$ 和 $$$v_i$$$,其边权为 $$$w_i$$$。

输入数据保证图是连通图。

Output:

输出一行一个正整数,即新图的最大权边独立集的边权和。

Sample Input:

4 1 7
1 2 8
2 3 4
2 4 6

Sample Output:

15

Info

CodeForces Gym

Provider CodeForces Gym

Origin 2021年中国大学生程序设计竞赛女生专场

Code GYM103389J

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 11/01/2021 22:24:41

Related

Nothing Yet