P1352 没有上司的舞会

题目描述

某大学有N个职员，编号为1~N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数Ri，但是呢，如果某个职员的上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

输入输出格式

输入格式：

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

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

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

最后一行输入0 0

输出格式：

输出最大的快乐指数。

输入输出样例

输入样例#1：

711111111 32 36 47 44 53 50 0

输出样例#1：

5 ——————————————————————————————————我是华丽丽的分割线———————————————————————————————— 树形动规果题。

1 /* 2     Problem:P1352 没有上司的舞会 3     OJ:        洛谷  4     User:    S.B.S. 5     Time:    27 ms 6     Memory: 16992 kb  7     Length: N/A 8 */ 9 #include
        
         10 #include
         
          11 #include
          
           12 #include
           
            13 #include
            
             14 #include
             
              15 #include
              
               16 #include
               
                17 #include
                
                 18 #include
                 
                  19 #include
                  
                   20 #include
                   
                    21 #include
                    
                     22 #include
                     
                      23 #include
                      24 #define F(i,j,k) for(int i=j;i<=k;i++)25 #define M(a,b) memset(a,b,sizeof(a))26 #define FF(i,j,k) for(int i=j;i>=k;i--)27 #define maxn 1000128 #define inf 0x3f3f3f3f29 #define maxm 100130 #define mod 99824435331 //#define LOCAL32 using namespace std;33 int read(){34 int x=0,f=1;char ch=getchar();35 while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();}36 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}37 return x*f;38 }39 int n,m;40 int x,y,k;41 int cnt,c[maxn],head[maxn];42 bool b[maxn];43 int f[maxn][2];44 vector 
                       
                         edge[maxn];45 void dfs(int u)46 {47 int a,b;48 for(int i=0;i
                        
                         >n;65 for(int i=1;i<=n;i++) cin>>c[i];66 int x,y;67 for(int i=1;i<=n;i++)68 {69 cin>>x>>y;70 if(x==0&&y==0) break;71 else72 {73 edge[y].push_back(x);74 b[x]=true;75 }76 }77 for(int i=1;i<=n;i++)78 {79 if(b[i]==false)80 {81 dfs(i);82 cout<
                         
                          <

p1352

转载于:https://www.cnblogs.com/SBSOI/p/5924177.html

你可能感兴趣的文章