T连通以后共享\sum_{u\in T}a_u，所以等价于缩点操作
首先考虑 Subtask 5，整个图是一个树的情况，考虑什么时候有解。
显然存在 引理. 对于一个树的情况有解当且仅当\sum a_u\geq \sum w_k
证明.先证必要性：无论什么时候，对于一个已经连通的集合\sum a_u-\sum w_k=x\geq 0恒定，最后连通也就是只剩下一个点的时候整个集合的权值是\geq 0的，得证。
充分性：对于一个|T|=n的集合，如果存在\sum a_u \geq \sum w_k，由不等式知一定存在至少一个边<u,v>:k，使得a_u+a_v\geq w_k，否则\sum a_u < \sum w_k；缩点后|T'|=n-1，归纳即可。所以不等式成立时解一定存在。
假如解一定存在，考虑合并的顺序。
最显然的O(n^2)暴力是每次选择一条a_{T_u}+a_{T_v} - w_{<u,v>}\geq 0的边暴力合并，但是我们已经知道了最后的结果一定是一个树(或者说单点)，因此对于任意一条边<u,v>:k，我们可以考虑边集\{E:T_u\cup T_v\}\cup \{k\}的合并顺序，设f(S)=\sum_{u\in S} a_u-\sum w_x，对于T_v,T_u分别有两种不同的取值情况：但是至少有其中一个集合S,f(S)\geq 0，那么由引理知S内一定存在一个方案使得S最后缩为1个点，可以优先缩点；如果f(S) < 0，那么就不存在方案使得S最后缩为一个点，又因为f(T_u)+f(T_v)-w_k\geq 0，所以另一侧的子树S'一定有f(S') - w_k>0，所以可以优先操作另一侧。两个集合T_u,T_v,f(T_u) < 0,f(T_v)<0都成立的情况是不存在的(由引理得)；如果两侧都>0，那么这条边一定可以放在最后操作。
分治跟暴力枚举的复杂度是一样的，在链的情况下会退化成O(n^2)
注意到分治当中对于一条边来说，他要么在两侧点所在集合合并之后再进行合并，要么优先进行合并。因此对于以一个点u为根的子树T来说也是类似的：设 u 的儿子集合是P，对于\forall v,v\in P,<u,v>:k，有f(T_v)-w_k \geq 0 || f(T_v)-w_k<0，对于第一种情况，合并后a_u->a_u +f(T_v)-w_k一定会\geq a_u；另一种情况则会变小。因为对于当前以u为根的子树T_u一有解，那么优先合并\geq 0的部分一定会使得答案合法。而对于<0的部分，因为已经合并了\geq 0的部分，所以无论按照怎样的顺序合并<0的部分，最后的结果一定\geq 0。但是对于合并的过程中，如上文对边分类讨论时所叙述的，如果两侧均\geq 0，那么当前边最后合并一定合法，否则如果对于以v,v\in P为根的子树合并前就合并<u,v>:k，可能会有f(T_u)+a_v-w_k<0的局面出现，此时合并序列不合法。
这样只需要预处理出所有的f，按照f-w\geq 0,<0;f(T_u)\geq 0|| f(T_v)\geq 0分类讨论即可。
对于普通图G:<V,E>的情况，显然在最小生成树上一定能得到\sum a_u-\sum w_k最大的解，使得答案尽量合法，因此优先做一次最小生成树即可。