程序设计思维与实践 Week6 作业 A 氪金带东

实验室里原先有一台电脑(编号为1)，最近氪金带师咕咕东又为实验室购置了N-1台电脑，编号为2到N。每台电脑都用网线连接到一台先前安装的电脑上。但是咕咕东担心网速太慢，他希望知道第i台电脑到其他电脑的最大网线长度，但是可怜的咕咕东在不久前刚刚遭受了宇宙射线的降智打击，请你帮帮他。

提示: 样例输入对应这个图，从这个图中你可以看出，距离1号电脑最远的电脑是4号电脑，他们之间的距离是3。 4号电脑与5号电脑都是距离2号电脑最远的点，故其答案是2。5号电脑距离3号电脑最远，故对于3号电脑来说它的答案是3。同样的我们可以计算出4号电脑和5号电脑的答案是4.

输入文件包含多组测试数据。对于每组测试数据，第一行一个整数N (N<=10000)，接下来有N-1行，每一行两个数，对于第i行的两个数，它们表示与i号电脑连接的电脑编号以及它们之间网线的长度。网线的总长度不会超过10^9，每个数之间用一个空格隔开。

对于每组测试数据输出N行，第i行表示i号电脑的答案 (1<=i<=N).

因为输入的每个点之连接了另外一个顶点，因此这是一道树的题目。

此题目需要用到树的直径：任意两点之间的距离最大值。

树的直径有下面的性质：

对于此题目，要输出每个点的距离最大值。最最最最简单的思路就是对每个点进行dfs，找出离他最远的点。但是复杂度为o(n*(n+m))，n为点数，m为边数，在树中，复杂度可计算为n*(n+n-1)，即O(n^2)，复杂度太高。

结合树的直径，某个点i的所到达的最长路径一定是dis(v1,i)或者是dis(v2,i)。因此本题的思路是，三遍dfs：

相当于在步骤二中计算了dis(v1,i)，在步骤三中计算了dis(v2,i)，最后对于每个i的最大距离ans=max(dis(v1,i),dis(v2,i)),输出ans即可。在代码中，dis(v1,i)为flor2[i]，dis(v2,i)为flor3[i]。

用链表存了整个树结构，总共用了三次dfs，因此时间复杂度为3(n+n-1)，即：O(n)

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,v1,v2,tot,ans1,ans2,ans3,head[10010];
int flor1[10010],flor2[10010],flor3[10010];
bool flag1[10010],flag2[10010],flag3[10010];
struct node
{
  int u;
  int v;
  int w;
  int next;
}e[20020];
void add_edge(int u,int v,int w)
{
  e[++tot].v=v;
  e[tot].w=w;
  e[tot].next=head[u];
  head[u]=tot;
}
void dfs1(int u)
{
  flag1[u]=1;
  for(int i=head[u];i;i=e[i].next)
  {
    int v=e[i].v;
    if(!flag1[v])
    {
      flag1[v]=1;
      flor1[v]=flor1[u]+e[i].w;
      if(flor1[v]>ans1)
      {
        ans1=flor1[v];
        v1=v;
      }
      dfs1(v);
    }
  }
}
void dfs2(int u)
{
  flag2[u]=1;
  for(int i=head[u];i;i=e[i].next)
  {
    int v=e[i].v;
    if(!flag2[v])
    {
      flag2[v]=1;
      flor2[v]=flor2[u]+e[i].w;
      if(flor2[v]>ans2)
      {
        ans2=flor2[v];
        v2=v;
      }
      dfs2(v);
    }
  }
}
void dfs3(int u)
{
  flag3[u]=1;
  for(int i=head[u];i;i=e[i].next)
  {
    int v=e[i].v;
    if(!flag3[v])
    {
      flag3[v]=1;
      flor3[v]=flor3[u]+e[i].w;
      if(flor3[v]>ans3)
      ans3=flor2[v];
      dfs3(v);
    }
  }
}
int main()
{
  int v,w;
  while(scanf("%d",&n)!=EOF)
  {
    memset(flag1,0,sizeof(flag1));
    memset(flag2,0,sizeof(flag2));
    memset(flag3,0,sizeof(flag3));
    memset(flor1,0,sizeof(flor1));
    memset(flor2,0,sizeof(flor2));
    memset(flor3,0,sizeof(flor3));
    memset(head,0,sizeof(head));
    ans1=0,ans2=0,ans3=0,tot=0;
    for(int i=2;i<=n;i++)
    {
      cin>>v>>w;
      add_edge(i,v,w);
      add_edge(v,i,w);
    }
    dfs1(1);
    dfs2(v1);
    dfs3(v2);
    for(int i=1;i<=n;i++)
    cout<<max(flor2[i],flor3[i])<<endl;
  }
  return 0;
}