T1

先排个序，当k=2时，肯定选左右两端的

之后每次贪心地选一个最小值，再选一个最大值，计入答案的话前缀和优化一下就行了

T3

线段树维护dfs序，定义几个变量：fm表示区间的归属点（同一个点就是它，不同为0），depmax表示区间所有点的归属点的最大深度，depmin反之

操作1,3板子

操作2,判断dep[k]和当前区间depmax的大小关系，\(dep[k]>depmax\)就return，否则一直递归到区间的fm为k。对于普通的树，复杂度\(\log n\)，但是可以被卡掉

操作4,若\(dep[k]< depmin\)，加上w然后return;若\(dep[k]>depmax\)就return;否则递归下去直到叶子。

操作5,6同理，利用depmax和depmin砍掉显然不合法的区间，然后进入存在合法区间的区间，将区间的fm修改