解题报告 P6082 [JSOI2015]salesman

题目内容

P6082

大意：给定一棵 n 个点的树，有点权，从 1 号点开始一次旅行，最后回到 1 号点。每到达一个点，就能获得等于该点点权的收益。每个点都有进入该点的次数限制，且每个点的收益只获得一次。求最大收益以及方案是否唯一。

解题思路

不难发现，这道题满足最优子结构，一棵子树的答案可由这棵子树的子树合并而来。

注意到进入限制这个性质，到达这个点进入了一次，去到每一棵子树再回来又是进入这个点一次，所以实际上我们只能访问这个点的 限制次数减一 棵子树。

而为了保证最优，需要使用贪心思想，当将一个节点的所有子树的信息处理完之后，将其从大到小排序，取前面的限制次数减一个并加起来（当然如果加到负数就肯定不加了）。

至于解的唯一性，注意到如果一个子树下的某个子树的解不唯一，那么这个子树的解肯定也不唯一。以及如果对于他的一棵子树，这个子树的答案为 0，则走与不走这个子树的效果是相同的，答案就会不唯一。还有，如果最后一个选的子树 a 的答案与下一个待选子树 b 的答案相同，说明可以选 a 也可以选 b，效果都是一样的，也会产生多解。

代码如下：

#include <utility>
#include <cstdio>
#include <cctype>
#include <queue>

using std::priority_queue;
using std::make_pair;
using std::vector;
using std::pair;

const int maxn=1e5+5;
int n,money[maxn],stop[maxn];
int f[maxn][2];

vector<int> g[maxn];

inline void ins(int from,int to)
{
    g[from].push_back(to);
    g[to].push_back(from);
    return;
}

inline int read()
{
    char c = getchar();
    int s = 0, x = 0;
    while (!isdigit(c))
    {
        if(c == '-')
            x = 1;
        c = getchar();
    }
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return x ? -s : s;
}

void dfs(int now,int fa)
{
    if(g[now].size()==1)//这是判断是否为叶子节点的
    {
        f[now][0]=money[now];
        return;
    }
    priority_queue<pair<int,int> > q;//排序用
    for(int i=0;i<g[now].size();i++)//访问下面的节点
    {
        if(g[now][i]!=fa)
        {
            dfs(g[now][i],now);//继续递归
            q.push(make_pair(f[g[now][i]][0],g[now][i]));//并且加入队列
        }
    }
    int lastChosen;
    for(int i=1; (!q.empty()) && (now==1 ? 1 : i<stop[now]);i++)
    {
        int to=q.top().second,val=q.top().first;
        if(val<0)//如果现在这棵子树已经小于 0 了，说明会产生负贡献，直接舍弃
            break;
        if(val==0)//有多解
            f[now][1]=1;
        f[now][0] += val;
        lastChosen=val;
        f[now][1] |= f[to][1];//下面的答案有多解的话也会产生多解
        q.pop();
    }
    f[now][0]+=money[now];
    if(q.size() && q.top().first==lastChosen)//如果下一个备选答案与上一个的相同，则有多解
        f[now][1]=1;
    return;
}

int main()
{
    n=read();
    for(int i=1;i<n;i++)
        money[i+1]=read();
    for(int i=1;i<n;i++)
        stop[i+1]=read();
    int from,to;
    for(int i=1;i<n;i++)
    {
        from=read(),to=read();
        ins(from,to);
    }
    dfs(1,0);
    printf("%d\n",f[1][0]);
    if(f[1][1])
        printf("solution is not unique\n");
    else
        printf("solution is unique\n");
    return 0;
}