bzoj4472,懒得复制，戳我戳我
Solution:
体面意思：从\(1\)号节点出发，每到一个节点就必须停下，获得节点权值（每个节点只会获得一次），每个点有个规定的停留次数，求最大可获得多大权值，并且判断是否只有唯一的路线才能获得这个权值
- 直接\(dp\)储存子树最大获得权值就行，顺便要记录方案是否唯一，所以我们可以拿一个结构体来记录
- \(dp\)权值思路：找出所有子树中前\(vis[i]-1\)大的节点权值（只选大于\(0\)的权值）。
- \(dp\)方案思路： 1.如果有选择的节点是方案不唯一的，该子树根节点也是方案不唯一。 2. 如果有子节点权值为\(0\)，该子树根节点方案不唯一。 3.如果选择的最后一个和不选择的第一个权值一样（且都大于\(0\)），该子树根节点方案不唯一。
Attention:
- 记录子树的结构体时用\(vector\)更好，不然容易超时越界一堆问题
（不会用\(vector\)强行卡代码时间卡过去了）
Code:
//It is coded by Ning_Mew on 4.22#include<bits/stdc++.h>using namespace std;const int maxn=1e5+7;int read(){ ?int x=0,f=1;char ch=getchar(); ?while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} ?while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar(); ?return x*f;}int n,val[maxn],fa[maxn],vis[maxn];struct Node{ ?int val;bool uni; ?Node(){val=0;uni=false;}}node[maxn];int head[maxn],cnt=0;struct Edge{int nxt,to;}edge[maxn*2];void add(int from,int to){ ?edge[++cnt].nxt=head[from]; ?edge[cnt].to=to; ?head[from]=cnt;}bool cmp(const Node &x,const Node &y){return x.val>y.val;}void dfs(int u){ ?bool son=false; ?Node box[maxn/128];int ct=0; ???for(int i=head[u];i!=0;i=edge[i].nxt){ ???int v=edge[i].to;if(v==fa[u])continue; ???fa[v]=u;son=true; ???dfs(v); ???ct++; box[ct]=node[v]; ?} ?if(!son){node[u].val=val[u]; node[u].uni=false;return;} ???sort(box+1,box+ct+1,cmp); ?for(int i=1;i<=min(vis[u]-1,ct);i++){ ???if(box[i].val>=0){ ?????node[u].val+=box[i].val; ?????if(box[i].uni)node[u].uni=true; ?????if(box[i].val==0){node[u].uni=true;break;} ???}else break; ?} ?node[u].val+=val[u]; ?if(vis[u]-1<ct&&box[ vis[u] ].val==box[ vis[u]-1 ].val&&box[ vis[u] ].val>=0)node[u].uni=true; ?return;}int main(){ ?//freopen("in.in","r",stdin); ?memset(head,0,sizeof(head));cnt=0; ?scanf("%d",&n); ?vis[1]=maxn; ?for(int i=2;i<=n;i++)/*val[i]=read();*/scanf("%d",&val[i]); ?for(int i=2;i<=n;i++)/*vis[i]=read();*/scanf("%d",&vis[i]); ?for(int i=1;i<=n-1;i++){ ???int u,v;/*u=read();v=read();*/scanf("%d%d",&u,&v); ???add(u,v);add(v,u); ?} ?dfs(1); ?printf("%d\n",node[1].val); ?if(!node[1].uni)printf("solution is unique\n"); ?else printf("solution is not unique\n"); ?return 0;}【题解】 bzoj4472: [Jsoi2015]salesman （动态规划）
原文地址：https://www.cnblogs.com/Ning-Mew/p/8930991.html