本文共 1079 字，大约阅读时间需要 3 分钟。

【题目描述】

政府邀请了你在火车站开饭店，但不允许同时在两个相连的火车站开。任意两个火车站有且只有一条路径，每个火车站最多有 50 个和它相连接的火车站。

告诉你每个火车站的利润，问你可以获得的最大利润为多少？

例如下图是火车站网络：

最佳投资方案是 1 ， 2 ， 5 ， 6 这 4 个火车站开饭店可以获得的利润为 90.

【输入格式】

第一行输入整数 N(<=100000), 表示有 N 个火车站，分别用 1,2,……..,N 来编号。接下来 N 行，每行一个整数表示每个站点的利润，接下来 N-1 行描述火车站网络，每行两个整数，表示相连接的两个站点。

【输出格式】

输出一个整数表示可以获得的最大利润。

【样例输入】

6 

10 

20 

25 

40 

30 

30 

4 5 

4 6 

3 4 

1 3 

2 3

【样例输出】

90

树形DP 此题不需要转化成二叉树（其实我也不会......）

由儿子的最大值推得父亲的最大值

原来写过一个类似的  上司的舞会

而且这次也写saca了

存反向边一开始s数组开的不够 导致RE7组

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int lim=100011;int m,root,z;int d[lim];struct self{int x,y;}s[lim*2];int first[lim*2],nxt[lim*2]; vector
         
          g[lim];int a,b,c;int f[lim][2];bool flag[lim]; void maketree(int i){ flag[i]=1; for(int e=first[i];e!=-1;e=nxt[e]) if(!flag[s[e].y]) { g[i].push_back(s[e].y); maketree(s[e].y); }} int work(int i,int chosen){ if(f[i][chosen]!=-1)return f[i][chosen]; if(chosen==0) { f[i][chosen]=0; for(int k=0;k
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/li412302070/article/details/12719237 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！