Chrysanthemum's Blog

本题本人现场就A了哟！！

比较简单，就不多讲了，注意一下第二问的一些细节就好了。

代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int n,u,v,tot,edgenum,ans,a[100010],f[100010],num[100010],q[100010],p[100010];
int vet[200010],next[200010],head[200010],ok[100010];
void add(int u,int v)
{
	edgenum++;
	vet[edgenum]=v;
	next[edgenum]=head[u];
	head[u]=edgenum;
}
bool cmp(const int x,const int y){return f[x]>f[y];}
void dfs(int u,int fa)
{
	int tot1=tot;
	f[u]=a[u];
	for (int e=head[u];e;e=next[e])
	{
		int v=vet[e];
		if (v!=fa) 
		{
			dfs(v,u);
			if (u==1){if (f[v]>0) {ans+=f[v];ok[1]=ok[1]|ok[v];}if (f[v]==0) ok[1]=1;}else q[++tot]=v;
		}
	}
	if (tot==tot1) return;
	if (u==1) return;
	for (int i=tot1+1;i<=tot;i++)
		p[i]=q[i];
	sort(p+tot1+1,p+tot+1,cmp);
	for (int i=tot1+1;i<=tot;i++)
	if (i-tot1>num[u]){if (i>tot1+1&&f[p[i]]==f[p[i-1]])ok[u]=1;break;}else if (f[p[i]]==0) ok[u]=1;else if (f[p[i]]<0) break;else {f[u]+=f[p[i]];ok[u]=ok[u]|ok[p[i]];}
	tot=tot1;
}
int main()
{
	freopen("salesman.in","r",stdin);
	freopen("salesman.out","w",stdout);
	scanf("%d",&n);
	for (int i=2;i<=n;i++)
		scanf("%d",&a[i]);
	for (int i=2;i<=n;i++)
	{
		scanf("%d",&num[i]);
		num[i]--;
	}
	for (int i=1;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	ans=0;
	dfs(1,0);
	printf("%d\n",ans);
	if (ok[1]) printf("solution is not unique\n");else printf("solution is unique\n");
}