PAT 1090

题目 ： Highest Price in Supply Chain (25)

分值 ： 25
难度 ： 简单题
思路 ： 找树的最深节点数
坑点 ： 如果遍历所有的叶子节点，然后向上维护一个max作为深度，会超时.需要优化.
亮点 ： 用了类似路径压缩的方法优化了时间复杂度，依旧从叶节点数往根上搜，但是路程中每个节点
       都只会经过一次.

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <math.h>
using namespace std ;
int chudu[100001];
int father[100001] ;
int deep[100001];

int find_source(int x)
{
    if(father[x] ==-1)
        return deep[x] = 1 ;
    if(deep[father[x] ]!=0)
        return deep[x] = deep[father[x]]+1 ;
    return deep[x] = find_source(father[x]) +1 ;
}

int main()
{
    int N ;
    double Price ,Rate;
    cin >> N >> Price >>Rate ;
    for(int i = 0 ; i< N ;i++)
    {
        int temp ;
        scanf("%d",&temp);
        father[i] = temp ;
        if(temp!=-1)
            chudu[temp] ++ ;
    }
    int max =0 ,count =0  ;
    for(int i = 0 ; i< N ; i++)
    {
        if(chudu[i] == 0 )
        {
            if(find_source(i) > max)
            {
                max = find_source(i);
                count =0 ;
            }
            if(find_source(i) == max)
                count ++ ;
        }
    }
    printf("%.2lf %d\n", Price*pow(1+Rate/100,max-1),count );

}