(\)
(Description)
给出一棵以(1)为根的(N)个节点的树，开始的时候你在(1)号节点。
除了(1)号节点以外，每个点都有访问次数限制(t_i)，即到达该点的次数上限。
除了(1)号点每个点还有一个权值(w_i)，这个权值可以是负的，每个点被第一次到达时你会被迫得到他的点权，以后该点点权变为(0)。
求满足所有次数上限的前提下，从(1)号点出发，最后回到(1)号点的一条路径所得到的最大点权和，每个点可以经过多次。
同时你还要输出这个最大点权和对应的方案是否唯一。
- (Nin [1,10^5])
(\)
(Solution)
-
第一问直接树形(DP)就好，从根节点到当前点的路径会消耗一次当前点的访问次数，而每次从子树回溯上来也会消耗一次访问次数，所以对于节点(u)，最多只能选(t_u-1)棵子树访问。直接(DFS)后将子树最大贡献排序，在所有正数答案里选前(t_u-1)个子树作为自己的答案。
-
关于方案唯一性的问题，维护一个(g)数组表示当前节点最优解是否唯一。转移时只要有一个子树方案数有多种当前节点的方案数就是多种。同时如果下一个要选择的子树（因为访问上限的关系不能选）和当前最后一个选择的子树答案相同，或者答案中选择了包含贡献为(0)的子树，方案也不是唯一的。
(\)
(Code)
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 100010
#define R register
#define gc getchar
#define inf 200000000
using namespace std;
inline int rd(){
int x=0; bool f=0; char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
return f?-x:x;
}
bool g[N];
int n,m,tot,hd[N];
int t[N],f[N],val[N],tmp[N];
struct edge{int to,nxt;}e[N<<1];
inline void add(int u,int v){
e[++tot].to=v; e[tot].nxt=hd[u]; hd[u]=tot;
}
inline bool cmp(int x,int y){return f[x]>f[y];}
void dfs(int u,int fa){
f[u]=val[u];
for(R int i=hd[u],v;i;i=e[i].nxt) if((v=e[i].to)!=fa) dfs(v,u);
tmp[0]=0;
for(R int i=hd[u],v;i;i=e[i].nxt) if((v=e[i].to)!=fa) tmp[++tmp[0]]=v;
sort(tmp+1,tmp+1+tmp[0],cmp);
int ptr=1,lim=min(tmp[0],t[u]-1);
while(ptr<=lim&&f[tmp[ptr]]>=0) f[u]+=f[tmp[ptr]],g[u]|=g[tmp[ptr]],++ptr;
if((ptr<=tmp[0]&&ptr>1&&f[tmp[ptr]]==f[tmp[ptr-1]])||(f[tmp[ptr-1]]==0&&ptr>1)) g[u]=1;
}
int main(){
n=rd();
for(R int i=2;i<=n;++i) val[i]=rd();
for(R int i=2;i<=n;++i) t[i]=rd();
for(R int i=1,u,v;i<n;++i){
u=rd(); v=rd(); add(u,v); add(v,u);
}
val[1]=0; t[1]=inf; dfs(1,0);
printf("%d
",f[1]);
puts(g[1]?"solution is not unique":"solution is unique");
return 0;
}