题解【BZOJ4472】[JSOI2015]salesman

题面

树形\(\text{DP}\)与贪心的结合。

首先考虑树形\(\text{DP}\)。

设\(dp_i\)表示从\(i\)出发，访问\(i\)的子树，并且最后回到\(i\)能获得的最大收益。

转移时优先挑选\(dp_j\)较大的\(j\)访问，直到用尽次数为止。

然后考虑解的唯一性。

我们发现这个东西是可以传递的，即：一个节点的子节点答案不唯一，那么这个节点的答案也不唯一。

如果当前访问到的节点与下一个要访问的节点\(dp\)值相同（可以与下一个节点交换访问顺序），或者它的\(dp\)值为\(0\)（可以不访问），那么这个节点的答案就不唯一。

如果按照我的写法就要注意一个问题：在递归时记录儿子个数的变量需要在第一轮遍历后清空，并且记录儿子。当然可以使用优先队列解决这个问题。

代码也很好写：

#include <bits/stdc++.h>

#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)

#define itn int

#define gI gi

using namespace std;

inline int gi()

{

	int f = 1, x = 0; char c = getchar();

	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}

	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return f * x;

}

const int maxn = 100003;

int n, m, tot, head[maxn], ver[maxn * 2], nxt[maxn * 2];

int sy[maxn], sj[maxn], son[maxn], sz, cnt;

int wy[maxn];

long long dp[maxn];

inline void add(int u, int v)

{

	ver[++tot] = v, nxt[tot] = head[u], head[u] = tot;

}

inline bool cmp(int x, int y) {return dp[x] > dp[y];}

void dfs(int u, int f)

{

	dp[u] = 1ll * sy[u];

	for (int i = head[u]; i; i = nxt[i])

	{

		int v = ver[i];

		if (v == f) continue;

		dfs(v, u);

	}

	cnt = 0; //注意要在这里清零

	for (int i = head[u]; i; i = nxt[i])

	{

		int v = ver[i];

		if (v == f) continue;

		son[++cnt] = v;

	}

	sort(son + 1, son + 1 + cnt, cmp);

	int now = 0;

	while (now < min(cnt, sj[u] - 1) && dp[son[now + 1]] >= 0)

		dp[u] += dp[son[++now]], wy[u] |= wy[son[now]];

	if ((now > 0 && now < cnt && dp[son[now]] == dp[son[now + 1]]) || (now > 0 && dp[son[now]] == 0))

		wy[u] = 1;

}

int main()

{

	//freopen(".in", "r", stdin);

	//freopen(".out", "w", stdout);

	n = gi();

	for (int i = 2; i <= n; i+=1) sy[i] = gi();

	for (int i = 2; i <= n; i+=1) sj[i] = gi();

	for (int i = 1; i < n; i+=1) {int u = gi(), v = gi(); add(u, v), add(v, u);}

	sj[1] = n + 1;

	dfs(1, 0);

	printf("%lld\n", dp[1]);

	if (wy[1]) puts("solution is not unique");

	else puts("solution is unique");

	return 0;

}

巴特西

题解【BZOJ4472】[JSOI2015]salesman

最新文章

热门文章