[codevs2170]悠闲的漫步

题目来源

http://www.tyvj.cn/p/1033

背景

USACO OCT09 5TH

描述

Bessie透过牛棚的大门向外望去。发现今天是一个美丽的春季早晨。她想，“我真的好想好想沐浴著春风，走在草地之中，感受嫩草温柔地抚摸四蹄地的感觉。”她知道一旦她离开了牛棚，她将沿著一条小径走一段路，然后就会出现一个三岔路口，她必须在两条小径中选择一条继续走下去。然后她又会遇到更多的三岔路口，进行更多的选择，知道她到达一个青翠的牧场為止。

她决定坐一个选择使得她在去吃早草的路途中可以走过最多的小径。给你这些小径的描述，要求Bessie最多可以走过多少条小径。假定Bessie一出牛棚就有2条路径，Bessie需要从中选择一条。

农场中有P-1 (1 <= P <= 1,000) 个分岔节点（范围是1..P），引向P片草地，它们之间由小径连接。对任意一个节点来说，只有一条从牛棚（被标记為节点1）开始的路径可以到达。

考虑下面的图。线段表示小径，"%"表示草地。右边的图中的"#"表示一条到达草地的高亮的路径。

                 %                             %
                /                             /
      2----%   7----8----%          2----%   7####8----%
     /       /                   # #      #      #
    1   5----6        9----%      1   5####6        9----%
                                              #
         %    %        %              %    %        %

        3-----%                       3-----%

          4----%                        4----%

            %                             %

从分岔节点9到达的草地是两个可以让Bessie走过最多小径的草地之一。在去吃早草的路上Bessie将走过7条不同的小径。这些草地是离牛棚也就是节点1最“远”的。

由3个整数来表示每一个节点：Cn, D1和D2，Cn是节点的编号(1 <= Cn <= P-1); D1和D2是由该节点引出的两条小径的终点(0 <= D1 <= P-1; 0 <= D2 <= P-1)。如果D1為0，表示这条小径引向的是一片牧草地；D2也一样。

输入格式

* 第1行: 一个单独的整数: P

* 第2到第P行: 第i+1行有3个由空格隔开的整数，表示一个分岔节点Cn, D1和D2。

输出格式

* 第一行: 一个单独的整数，表示Bessie去最远的草地的路上最多可以走过的小径的数目。

测试样例1

输入

10
7 8 0
5 0 6
9 0 0
6 0 7
3 4 0
2 5 0
8 0 9
4 0 0
1 2 3

输出

7

备注

1-2-5-6-7-8-9-P是最长的一条路径之一。

思路

　　搜索就可以过，仔细思考一下这个题可以发现就是一棵树从根节点到他的任意一个子节点的最长路径。我写了一个在水不过的DFS，应该可以有其他方法的。

　　PS：作为一个强迫症患者，我无法容忍存节点的数组是无序的，所以在时间允许的情况下，我把它们按序号排了一个序，虽然没有什么卵用吧，然而看着顺眼。

type tree=record
    r,l,f,num:longint;
    end;

var a:array[-1..1000] of tree;
    i,j,n,x,y,z,sum,ans:longint;

function max(x,y:longint):longint;
begin
    if x<y then exit(y) else exit(x);
end;

procedure dfs(x:longint);
var i,j,k:longint;
begin
    if (a[x].l=0)and(a[x].r=0) then
        begin
            inc(sum);
            ans:=max(ans,sum);
            exit;
        end;
    if (a[x].l=0) then
        begin
           inc(sum);
           ans:=max(ans,sum);
           dec(sum);
        end;
    if (a[x].r=0) then
        begin
           inc(sum);
           ans:=max(ans,sum);
           dec(sum);
        end;
    inc(sum);
    dfs(a[x].r);
    dec(sum);
    dfs(a[x].l);
    dec(sum);
end;

procedure sort(l,r: longint);
      var
         i,j,x:longint;y:tree;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2].num;
         repeat
           while a[i].num<x do
            inc(i);
           while x<a[j].num do
            dec(j);
           if not(i>j) then
             begin
                y:=a[i];
                a[i]:=a[j];
                a[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;

procedure init;
var i,j:longint;
begin
    readln(n);
    for i:=1 to n-1 do
        begin
            readln(x,y,z);
            a[i].num:=x;
            a[i].l:=y;
            a[i].r:=z;
        end;
end;

begin
    ans:=-1;sum:=0;
    init;
    sort(1,n-1);
    dfs(1);
    writeln(ans);
end.

View Code