A. Graph

在树的情况下，答案是显然的。

一次dfs，尽量将子树内不同的边合并就可以了。

考虑非树的情况，可以生成一棵树。

将非树边任意加在一个端点上，视作点权加一。

对于树上的每一个点，先考虑它的子节点，子节点的父边尽量在子节点处作连接节点使用。

如果子节点的父边还没有被使用，那么只能在父节点处使用。

同时将该节点的点权不断使用。

正确性是显然的，因为对于每一个联通块，都可以形成足够的边对。

B. Permutation

考虑怎样的一些点对$(i,j)$，它们之间不能交换。

将所有不能交换的点对建边，跑出最优的拓扑序就是最优解。

然而这样建图是$n^2$的，很难优化。

考虑换一种方式建边。

因为原序列是一个排列，可以处理出数组$pos$，使$pos_{a_i}=i$

于是原图中的边在$pos$数组下标的形式下转化为了简单的形式。

$$i<j$$

$$abs(pos_i-pos_j)<k$$

然而暴力建边仍然$n^2$，

一个很好的性质是：在$pos$的限制下，每个点建边区间范围是相同的。

所以倒序建边，每个点只要向$pos$意义下左右两侧最小的j建边就可以了。

然而值得注意的是，对于一个排列，$pos$意义下更小，不意味着原数组更小。

本题中实际上是利用了特殊性质，因为会不断交换合法的点，使得不存在使原数组更小的情况。

C. Tree

答案为边权之和。

不妨考虑最优答案应当是怎样的。

每一条权值较小的边应当被尽量少的次数经过，所以应当尽量先取权值大的边。

想一想就可以知道：

最优答案一定不会大于边权之和。

因为对于任何一个排列，每条边至少会经过一次。

存在一种构造方式，构造出边权之和。

使最大边权所连的点入队，不断取出队中的点所连的最大边权，并将新点入队。

这样形成的排列，边权不断减小，所以每条边都被充分利用，所以是正确的。