某售货员小T要到若干城镇去推销商品,由于该地区是交通不便的山区，任意两个城镇

之间都只有唯一的可能经过其它城镇的路线。 小T 可以准确地估计出在每个城镇停留的净收

益。这些净收益可能是负数，即推销商品的利润抵不上花费。由于交通不便，小T经过每个

城镇都需要停留，在每个城镇的停留次数与在该地的净收益无关，因为很多费用不是计次收

取的，而每个城镇对小T的商品需求也是相对固定的，停留一次后就饱和了。每个城镇为了

强化治安，对外地人的最多停留次数有严格的规定。请你帮小T 设计一个收益最大的巡回方

案,即从家乡出发，在经过的每个城镇停留，最后回到家乡的旅行方案。你的程序只需输出

最大收益，以及最优方案是否唯一。方案并不包括路线的细节，方案相同的标准是选择经过

并停留的城镇是否相同。因为取消巡回也是一种方案，因此最大收益不会是负数。小T 在家

乡净收益是零，因为在家乡是本地人，家乡对小 T当然没有停留次数的限制。

树上贪心

dp[x],表示以x为根的子树的最大值，g[x]表示dp[x]确定最大时,是否出现方案有多个(只要判断最优方案中某个可选的do值为0)

每层维护一个堆，将dp[y],g[y]，扔进堆中，取前cnt[x] - 1个，直到有0出现为止

code:

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int MAXX = 100100;int hed[MAXX], ver[MAXX << 1], nxt[MAXX << 1], val[MAXX], cnt[MAXX], dp[MAXX];bool g[MAXX];int n, tot;inline void add(int x, int y) {  ver[++tot] = y;  nxt[tot] = hed[x];  hed[x] = tot;}inline void dfs(int x,int f) {  priority_queue
        
         
           > q; for (int i = hed[x]; i; i = nxt[i]) { int y = ver[i]; if (y == f) continue; dfs (y, x); q.push(make_pair(dp[y],g[y])); } int num = 0; int now = 0; bool flag = 0; while (!q.empty() && num < cnt[x] - 1) { if(q.top().first < 0) break; else if (q.top().first == 0) { flag |= 1; break; }else { now += q.top().first; flag |= q.top().second; } q.pop(); num++; } dp[x] = now + val[x]; g[x] = flag; }int main() { scanf("%d", &n); cnt[1] = 1e9; for (int i = 2; i <= n; ++i) scanf("%d", &val[i]); for (int i = 2; i <= n; ++i) scanf("%d", &cnt[i]); for (int i = 1; i < n; ++i) { int x, y; scanf("%d%d", &x, &y); add(x, y); add(y, x); } dfs(1, 0); printf("%d\n",dp[1]); if (g[1] == 0) printf("solution is unique"); else printf("solution is not unique"); return 0;}