题目大意：对于一棵n个结点的无根树，求出每个结点的最远点，要求时间复杂度为O(n)。

对于一个点，距离它最远的点一定是直径的端点。
证明：我们求直径的时候，两次dfs。
两次bfs（或者dfs）
方法：先从任意一点P出发，找离它最远的点Q，再从点Q出发，找离它最远的点W，W到Q的距离就是是的直径

①若P已经在直径上，根据树的直径的定义可知Q也在直径上且为直径的一个端点

②若P不在直径上，我们用反证法，假设此时WQ不是直径，AB是直径

—>若AB与PQ有交点C，由于P到Q最远，那么PC+CQ>PC+CA，所以CQ>CA，易得CQ+CB>CA+CB，即CQ+CB>AB，与AB是直径矛盾，不成立，如下图（其中AB，PQ不一定是直线，画成直线是为了方便）：

—>若AB与PQ没有交点，M为AB上任意一点，N为PQ上任意一点。首先还是NP+NQ>NQ+MN+MB，同时减掉NQ，得NP>MN+MB，易知NP+MN>MB，所以NP+MN+MA>MB+MA，即NP+MN+MA>AB，与AB是直径矛盾，所以这种情况也不成立，如下图：

那么这个就已经证明了。

我们现在只需要把两个端点求出来，然后对两个端点进行两次dfs，更新他们到端点的距离，然后取最大值的就行了。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;

struct E
{
    int to;
    int w;
    E(int a, int b)
    {
        to=a;
        w=b;
    }
};

vector<E> e[maxn];
int dp[maxn][2];
int d, k;
int vis[maxn];

int dfs(int u, int s, int f)
{
    vis[u]=1;
    dp[u][f]=s//保存到端点的距离
    if(s>d)
    {
        d=s, k=u;
    }
    for(int i=0;i<e[u].size();i++)
    {
        int v=e[u][i].to, w=e[u][i].w;
        if(!vis[v])
        {
            dfs(v, s+w, f);
        }
    }
}

int main()
{
    int u, v, w, d1, d2;
    memset(vis, 0, sizeof(vis));
    memset(dp, 0, sizeof(dp));
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        e[u].push_back(E(v, w));
        e[v].push_back(E(u, w));
    }

    d=k=0;
    dfs(1, 0, 0);
    d1=k;//第一个端点
    
    memset(vis, 0, sizeof(vis));
    dfs(d1, 0, 0);
    
    d2=k;//第二个端点
    memset(vis, 0, sizeof(vis));
    dfs(d2, 0, 1);
    

    for(int i=1;i<=n;i++)
    {
        //输出距离最远的点，和最大距离
        cout<<(dp[i][0]>dp[i][1]?d1:d2)<<max(dp[i][0], dp[i][1])<<endl;
    }

    return 0;
}