[吼吼]加工树枝

时间：2010-09-23 来源：雲中君

【描述】

Dragon同学一天捡到了一根非常非常巨大的树枝，于是同学就想啊，如果把这根树枝多余的分叉剔掉最后剩下一根没有分叉的木棍，用它自卫就没人敢欺负我们科学家了呀：）

你的任务是，对给定树枝，求出它包含的最长木棍。

【输入格式】

第一行一个正整数n，表示顶点数，顶点从1至n编号。

然后n – 1行每行两个正整数u, v表示u, v之间有一条边，每条边的长度为1。

保证输入的是一棵树。

【输出格式】

只有一行，表示给定树的最长链长度。

【样例输入】

1 2

1 3

1 4

1 5

【样例输出】

【分析】

很明显，求树中的最长链。设f[i]是i的子树中最远的点到自己的距离，p[i]是第二远的点到自己的距离。那么所有的点钟最大的f[i]+p[i]就是答案。

第一次写——临边表。显然存不下。

第二次写——模拟链表。用的递归造树，爆掉。

想到了要用手工的栈。

可是我不知道怎么写囧。

于是看了标程。

原来还可以这么构树！！！

原来手工栈这么写！！！

顿悟。

第三次——AC。

#include <stdio.h>
#include <stdlib.h>
#define maxn 1000010

int f[maxn];
int father[maxn],str[maxn];
struct ss
{
       int num,next;
} a[maxn];
int tot,n,u,v,p,ans;
int c[maxn],deep[maxn],sta[maxn],top,e[maxn],te;

void ins(int x,int y)
{
     a[++tot].num=y;
     a[tot].next=str[x];
     str[x]=tot;
}

int cmp(const void*a,const void*b)
{
    int c=*(int*)a,d=*(int*)b;
    if (deep[c]<deep[d]) return -1;
    if (deep[c]>deep[d]) return 1;
    return 0;
}

int main()
{
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    
    scanf("%d",&n);
    for (int i=1;i<n;++i)
    {
        scanf("%d%d",&u,&v);
        ins(u,v);
        ins(v,u);
    }
    
    sta[0]=1;
    e[0]=str[1];
    father[1]=0;
    while (top>=0)
    {
          te=e[top];
          if (!te) --top;
          else
          {
              v=sta[top];
              u=a[te].num;
              e[top]=a[te].next;
              if (u!=father[v])
              {
                          sta[++top]=u;
                          e[top]=str[u];
                          deep[u]=deep[v]+1;
                          father[u]=v;
              }
          }
    }
    
    for (int i=1;i<=n;++i) c[i]=i;
    deep[0]=-1;
    qsort(c,n+1,sizeof(int),cmp);
    for (int i=n;i>0;--i)
    {
        u=c[i];
        te=str[u];
        if (!te) continue;
        p=0;
        do
        {
                 v=a[te].num;
                 if (father[u]!=v)
                    if (f[v]+1>f[u])
                    {
                                  p=f[u];
                                  f[u]=f[v]+1;
                    }
                    else 
                         if (f[v]+1>p) p=f[v]+1;
                 te=a[te].next;
        }
        while (te);
        if (f[u]+p>ans) ans=f[u]+p;
    }
    
    printf("%d\n",ans);
    
    return 0;
}