BZOJ4472[Jsoi2015] salesman 解题报告【树形DP】

本文主要是介绍BZOJ4472[Jsoi2015] salesman 解题报告【树形DP】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description
某售货员小T要到若干城镇去推销商品,由于该地区是交通不便的山区，任意两个城镇之间都只有唯一的可能经过其它城镇的路线。小T 可以准确地估计出在每个城镇停留的净收益。这些净收益可能是负数，即推销商品的利润抵不上花费。由于交通不便，小T经过每个
城镇都需要停留，在每个城镇的停留次数与在该地的净收益无关，因为很多费用不是计次收取的，而每个城镇对小T的商品需求也是相对固定的，停留一次后就饱和了。每个城镇为了强化治安，对外地人的最多停留次数有严格的规定。请你帮小T 设计一个收益最大的巡回方案,即从家乡出发，在经过的每个城镇停留，最后回到家乡的旅行方案。你的程序只需输出最大收益，以及最优方案是否唯一。方案并不包括路线的细节，方案相同的标准是选择经过并停留的城镇是否相同。因为取消巡回也是一种方案，因此最大收益不会是负数。小T 在家乡净收益是零，因为在家乡是本地人，家乡对小 T当然没有停留次数的限制。
Input
输入的第一行是一个正整数ｎ(5<=n<=100000)，表示城镇数目。城镇以１到ｎ的数命名。小T 的家乡命名为１。第二行和第三行都包含以空格隔开的ｎ－１个整数，第二行的第ｉ个数表示在城镇ｉ＋１停留的净收益。第三行的第ｉ个数表示城镇ｉ＋１规定的最大停留次数。所有的最大停留次数都不小于２。接下来的ｎ－１行每行两个１到ｎ的正整数ｘ，ｙ，之间以一个空格隔开，表示ｘ，ｙ之间有一条不经过其它城镇的双向道路。输入数据保证所有城镇是连通的。
Output
输出有两行，第一行包含一个自然数，表示巡回旅行的最大收益。如果该方案唯一，在第二行输出“solution is unique”，否则在第二行输出“solution is not unique”。
Sample Input
9
-3 -4 2 4 -2 3 4 6
4 4 2 2 2 2 2 2
1 2
1 3
1 4
2 5
2 6
3 7
4 8
4 9
Sample Output
9
solution is unique
//最佳路线包括城镇 1，2， 4， 5， 9。
解题报告
首先我们要看到，对于所谓一个点到达的次数的限制意味着什么，显然，这意味着我们只能访问lim[u]-1颗u的子树。贪心地，我们的答案就dp[u]应该是由大到小地加上lim[u]-1颗子树（如果有这么多的话）的答案。
那么答案是否唯一如何判定呢？对于一个节点u，若dp[u]不唯一则有这两种情况：其子树中我们选择的节点的答案和我们没选的答案相同（可以替代）；子树中最小的答案为0（这就意味着我们可以不访问这颗子树）。
此外还需要明确一点：对于一个点u，他的答案是否唯一还可以通过其子树的答案是否唯一来传递。
代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100000;
struct edge
{int v,next;
}ed[2*N+5];
int n,w[N+5],lim[N+5];
int dp[N+5],g[N+5],temp[N+5],tot;
int head[N+5],num;
void build(int u,int v)
{ed[++num].v=v;ed[num].next=head[u];head[u]=num;
}
bool cmp(int a,int b){return dp[a]>dp[b];}
void dfs(int u,int f)
{dp[u]=w[u];for(int i=head[u];i!=-1;i=ed[i].next){int v=ed[i].v;if(v==f)continue;dfs(v,u);}tot=0;for(int i=head[u];i!=-1;i=ed[i].next){int v=ed[i].v;if(v==f)continue;temp[++tot]=v;//保存其子树的编号 }sort(temp+1,temp+1+tot,cmp);//按收益从大到小排序 int p=0;while(p<min(lim[u]-1,tot)&&dp[temp[p+1]]>=0)dp[u]+=dp[temp[++p]],g[u]|=g[temp[p]];//1 or 1=1,1 or 0=1 if(p<tot&&p>0&&dp[temp[p]]==dp[temp[p+1]]||dp[temp[p]]==0&&p>0)g[u]=1;//答案不唯一的两种情况 
}
int main()
{scanf("%d",&n);memset(head,-1,sizeof(head));for(int i=2;i<=n;i++)scanf("%d",&w[i]);for(int i=2;i<=n;i++)scanf("%d",&lim[i]);for(int i=1;i<=n-1;i++){int u,v;scanf("%d%d",&u,&v);build(u,v);build(v,u);}lim[1]=n+1;dfs(1,0);printf("%d\n",dp[1]);if(g[1])printf("solution is not unique\n");else printf("solution is unique\n");return 0;
}