本题的思路有很多，这里只介绍一种：

最大生成树（Kruskal）

算法思路：

就是Kruskal的常规思路：

先是排序，再是用并查集连边，最后输出最大边权。

sort(e+1,e+1+m,cmp);for(int i=1;i<=m;++i){    f=find(e[i].f);    t=find(e[i].t);    if(f!=t)    {        b[f]=t;        ++cnt;        w=find(1);        if(t==w)        {            for(int j=2;j<=n;++j)            {                if(ok[j]==false&&find(j)==w)                {                    ans[j]=e[i].w;                    ok[j]=true;                }            }            if(cnt==n-1)            {                break;            }        }    }}

Q1：本题为什么要用最大生成树（Kruskal）？

A1：因为只需要判断每一个点在生成最大生成树的时候，是否与$1$联通，如果联通了，那么他的答案就是当前边（因为边是按权值从大到小排列的，当前边就是当前点与$1$中最小的边）。