没有上司的舞会

 

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 钻石 Diamond

 

 

 

题目描述 

Description

      Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。

输入描述 

Input Description

第一行一个整数N。(1<=N<=6000)

接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)

接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。

最后一行输入0,0。

输出描述 

Output Description

输出最大的快乐指数。

样例输入 

Sample Input

7

1

1

1

1

1

1

1

1 3

2 3

6 4

7 4

4 5

3 5

0 0

样例输出 

Sample Output

5

数据范围及提示 

Data Size & Hint

各个测试点1s

——————————————————我是华丽丽的分割线——————————————————————

水题，很坑。

标程用的是数组模拟邻接表，但STL大法好（\(^o^)/~），vector秒杀。。。

存储后从上往下递归，依次计算。

还有一个坑点，在洛谷上数据范围不能信。开6000的数组有4个点会RE，必须开10000的数组才能AC。

代码如下：

1 #include
           
             2 #include
            
              3 #include
             
               4 #include
              
                5 #include
               
                 6 #include
                
                  7 #include
                 
                   8 #include
                  
                    9 #include
                   
                    10 #include
                    
                     11 #include
                     
                      12 #define maxn 1000113 using namespace std;14 int read(){15 int x=0,f=1;char ch=getchar();16 while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();}17 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}18 return x*f;19 }20 int n,x,y,k;21 int cnt,c[maxn],head[maxn];22 bool b[maxn];23 int f[maxn][2];24 vector 
                      
                        edge[maxn];25 void dfs(int i)26 {27 int a,b;28 for(int j=0;j
                       
                        >n;43 for(int i=1;i<=n;i++) cin>>c[i];44 int x,y;45 for(int i=1;i<=n;i++)46 {47 cin>>x>>y;48 if(x==0&&y==0) break;49 else50 {51 edge[y].push_back(x);52 b[x]=true;53 }54 }55 for(int i=1;i<=n;i++)56 {57 if(b[i]==false)58 {59 dfs(i);60 cout<
                        
                         <