点分治好题。

题意简述：给一棵带边权的树，问所有路径中前$m$大的。$m\le 300000$

---

思路：

网上有题解写了可以通过什么点分治序转化成超级钢琴那道题的做法蒟蒻吓得瑟瑟发抖。

然后由于我比较菜想了一个二分答案的方法。

我们二分第$m$大的值，每次用点分治检验合法性。

二分完了之后我们再跑一次点分统计答案。

然后第一个二分的时候直接做是logn3log^3_nlogn3​的。

考虑降下来一个$log$。

我们先$dfs$一次树把每个点作为重心的时候的所有$dist$预处理下来就可以省掉一个$log$啦！ 空间复杂度O(nlogn)233

代码：

#include
    
     #define ri register int#define fi first#define se secondusing namespace std;inline int read(){
    	int ans=0;	char ch=getchar();	while(!isdigit(ch))ch=getchar();	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();	return ans;}typedef long long ll;typedef pair
     
       pii;const int N=5e4+5,M=3e5+5;int n,m,siz[N],msiz[N],stk[M],top=0,rt,all,Rt;bool vis[N];vector
      
       e[N];vector
       
        dis[N],g[N],inv[N];ll ans;priority_queue
        
         ANS;void getroot(int p,int fa){
    	siz[p]=1,msiz[p]=0;	for(ri i=0,v;i