【题解】

　　考虑从小到大枚举边权，按顺序加边。

　　当前树被分成了若干个联通块，若各个块内的点只能跟块外的点匹配，那么最终的min g(i,pi)一定大于等于当前枚举的边。

　　判断各个联通块内的点是否全部能跟块外的点匹配，只需比较sum-cnt[i]、size[i]，其中sum是所有x的和，cnt是块内x的和，size是联通块大小。

1 #include
     
       2 #include
      
        3 #include
       
         4 #define LL long long 5 #define rg register 6 #define N 200010 7 using namespace std; 8 int n,ans,f[N],siz[N]; 9 LL cnt[N],sum;10 struct edge{
   int u,v,w;}e[N];11 inline int read(){12     int k=0,f=1; char c=getchar();13     while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();14     while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();15     return k*f;16 } 17 inline bool cmp(edge a,edge b){
   return a.w
        
         =siz[u]&&sum-cnt[v]>=siz[v]) ans=max(ans,e[i].w);29         else break;30         f[u]=v; cnt[v]+=cnt[u]; siz[v]+=siz[u];31         if(sum-cnt[v]