bzoj4472:[Jsoi2015]salesman

传送门

树形dp

对于每个点维护其子节点的走法是否唯一，每次取最大的并且不为负的(停留次数-1)个子儿子权值，然后判断走法是否唯一

假如有子节点的权值为0，走法也不唯一

代码：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<vector>

#include<cstring>

using namespace std;

void read(int &x) {

	char ch;bool ok;

	for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;

	for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar());

	if(ok) x=-x;

}

#define rg register

const int maxn=1e5+10;

vector<pair<int,int> >s[maxn];

int n,m,f[maxn],pre[maxn*2],nxt[maxn*2],h[maxn],a[maxn],b[maxn],cnt,top;bool g[maxn];

void add(int x,int y)

{

	pre[++cnt]=y,nxt[cnt]=h[x],h[x]=cnt;

	pre[++cnt]=x,nxt[cnt]=h[y],h[y]=cnt;

}

void dfs(int x,int fa)

{

	f[x]=a[x];g[x]=0;b[x]--;

	if(!b[x])return ;

	for(rg int i=h[x];i;i=nxt[i])

		if(pre[i]!=fa)dfs(pre[i],x),s[x].push_back(make_pair(f[pre[i]],g[pre[i]]));

	sort(s[x].begin(),s[x].end());int now=0,t=s[x].size();

	for(rg int i=1;i<=b[x];i++)

	{

		if(now==t||s[x][t-now-1].first<0)break;

		if(!s[x][t-now-1].first)g[x]=1;

		else g[x]|=s[x][t-now-1].second,f[x]=f[x]+s[x][t-now-1].first;

		now++;

	}

}

int main()

{

	read(n);b[1]=1e9;

	for(rg int i=2;i<=n;i++)read(a[i]);

	for(rg int i=2;i<=n;i++)read(b[i]);

	for(rg int i=1,x,y;i<n;i++)read(x),read(y),add(x,y);

	dfs(1,0),printf("%d\n",f[1]);

	if(g[1])printf("solution is not unique\n");

	else printf("solution is unique\n");

}

巴特西

bzoj4472:[Jsoi2015]salesman

传送门

最新文章

热门文章