题目：

　　　

学习（抄）了 hzwer 的代码，觉得写得很好。

有一个 “如果排序后第 i 个关键点和第 i-1 个关键点的 lca 是第 i-1 个关键点，就舍弃第 i 个关键点” 的操作，觉得很好。

把 hd[ ] 数组清空写在了 dfs 里，觉得很好。

自己一开始写了一个倍增找链上边权最小值，用来给虚树的边赋值，参考之后发现只要记录一个 “到根的路径上的最小边权” 就行了。

#include
     
      #include
      
       #include
       
        #define ll long longusing namespace std;int rdn(){  int ret=0;bool fx=1;char ch=getchar();  while(ch>'9'||ch<'0'){
   if(ch=='-')fx=0;ch=getchar();}  while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();  return fx?ret:-ret;}ll Mx(ll a,ll b){
    return a>b?a:b;}ll Mn(ll a,ll b){
    return a
        
         =0;t--)    if(pre[x][t]!=pre[y][t])      x=pre[x][t],y=pre[y][t];  return pre[x][0];}namespace Tr{  int hd[N],xnt,to[N],nxt[N];  int p[N],tot,sta[N],top; ll dp[N];  void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}  void get_tr()  {    xnt=0;    sort(p+1,p+tot+1,cmp);    int lm=tot; p[tot=1]=p[1];    for(int i=2;i<=lm;i++)      if(get_lca(p[i],p[tot])!=p[tot])p[++tot]=p[i];    sta[top=1]=1;    for(int i=1;i<=tot;i++)      {    int u=p[i], lca=get_lca(u,sta[top]);    while(top&&dfn[lca]