记c(x,y)表示边权。
对T_2进行点分治
设x,y在当前点分树中到根的距离为dep_x,dep_y
那么我们可以认为(x,y)的边权为dist_1(x,y)+dep_x+dep_y
因为，若在当前点分树中，lca(x,y)等与点分树的重心，那么上式是成立的，否则c(x,y)\leq dist_1(x,y)+dep_x+dep_y
真实的c(x,y)会递归进下一个点分树被考虑到，我们可以认为这个式子依然成立，对答案不会有影响
那么我们希望在当前点分树的意义下删除一些一定不会对最终答案有贡献的(x,y)
考虑以下算法：
1.首先求出当前点分树中的点，在T_1当中的虚树。
2.对于所有当前点分树中的点x,建立新点x',在虚树上加一条(x,x')边，边权为dep_x，我们称mp[x']=x,我们称所有这样的x'为源点
3.跑两遍树dp,对于虚树上每个点y，记录pre[y]表示离y最近的源点（如果有多个最近的随便记一个即可），dist[y]表示pre[y]与y的距离
4.枚举虚树中每一条边(a,b)，将(mp[pre[a]],mp[pre[b]],dist[a]+dist[b]+l(a,b))，l表示虚树上一条边的长度。这条边加入候选边集
所有点分树的所有候选边集大小总共O(n\log n)，对这些边进行kruskal算法，即可算出答案。
使用预处理ST表求lca可在O(n\log n)选出候选边集。
算法正确性证明请读者自行思考。
算法复杂度O(n\log n+n\log n\log (n\log n))
后面那第二个\log只是给n\log n条边排序的复杂度，众所周知sort排序是很快的，因此此算法可在一定意义上认为是O(n\log n)。std是基于这种做法，因此很多使用boruvka算法或其他做法的O(n\log^2n)可能会被卡常，实际上时限非常宽松。
按照此算法，atcoder上的那个子问题可做到O(n)