题解【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

原文：https://www.cnblogs.com/xsl19/p/12267077.html