题解 P6082 【[JSOI2015]salesman】

· · 题解

分析

题目中的任意两个城镇之间都只有唯一的可能经过其它城镇的路线非常重要，这就说明题目中给出的图一定是一棵树

因此，联系最近学过的内容，我们可以用树形DP求解

题目中给出了停留次数的限制，这其实就是给出了你最多能访问多少子树

注意：在一个节点停留n次说明你可以遍历n-1棵子树，因为你还要从子树返回这一个节点，所以在读入时要w--（为了方便，后文的停留次数都是指--之后的）

那么动态转移方程是什么呢？

其实很简单，就是在停留次数限制内选择价值最大的子树，同时如果一个子树的价值为负，那么我们就不能选

比如上面这幅图，如果在父亲节点只能停留1次，则我们要选择价值最大的节点5

如果停留2次，我们要选择价值最大的两个节点5、3

如果停留3次呢，我们是选择5、3、-1吗？显然不是，因为选择-1这个点会拉低价值，所以我们只选5、3两个点就可以

知道了怎么选择节点，我们来看一下什么情况会出现多种选择

1、既然是重复，那么两个节点价值相同的情况一定要考虑一下

我们看上面这幅图

如果在父亲节点只能停留1次，则我们会有两种情况：选左边的5或者右边的5

如果停留2次，我们只有一种情况：两个5都选

如果停留3次，我们也有两种情况：选上2个5，左边的4和右边的4再任选一个

停留4次呢？又只有一种了

所以，只有当父亲节点剩余的停留次数为1，而且此时最大值有两个及以上儿子节点，那么就会有多种情况

2、子节点的价值为零 这种情况比较特殊，因为无论你选没选到他，价值都是一样，所以会有两种选择

但是前提是价值为0的节点必须前k大的节点之内，因为如果你都遍历不到他，更谈不上决策了

记录子节点的最大值我们用优先队列就可以

代码 把这两种情况搞清之后，我们就可以开始写代码了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
using namespace std;
const int maxn=2e5+5;
struct asd{
    int from,to,next;
}b[maxn];
int tot=1,head[maxn];
int da[maxn],cx[maxn];
void ad(int aa,int bb){
    b[tot].from=aa;
    b[tot].to=bb;
    b[tot].next=head[aa];
    head[aa]=tot++;
}//建边
int f[maxn];//记录最大值
int jud;
void dfs(int now,int fa){
    priority_queue<int> q;//默认大根堆
    for(int i=head[now];i!=-1;i=b[i].next){
        int u=b[i].to;
        if(u==fa) continue;
        dfs(u,now);
        q.push(f[u]);//遍历，同时将子节点的值pop进去
    }
    int cnt=0,jl=0x3f3f3f3f;
    if(q.size()>=2){
        int xx=q.top();
        q.pop();
        jl=q.top();
        q.push(xx);
    }
    //cnt记录所选元素的个数，jl记录上一次选的元素
    //这道题数据很水，把jl赋值成0x3f3f3f3f都能过
    //下面是错误写法
    /*
    int cnt=0,jl=0x3f3f3f3f;或者jl=0;jl=任何数
    没有后面的判断
    虽然能过，但是不对
    */
    while(!q.empty()){
        cnt++;
        int xx=q.top();
        if(xx==0 || (cx[now]==cnt && jl==xx)){
            jud=1;
        }//有两种决策的情况
        if(xx<0 || cx[now]+1==cnt) break;//超过停留次数
        f[now]+=xx;
        jl=xx;
        q.pop();//一定要pop
    }
    while(!q.empty()) q.pop();//pop不pop都可以
}
int main(){
    memset(head,-1,sizeof(head));
    int n;
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        scanf("%d",&da[i]);
    }
    for(int i=2;i<=n;i++){
        scanf("%d",&cx[i]);
        cx[i]--;//一定要--
    }
    cx[1]=0x3f3f3f3f;//1号节点可以停留无数次
    for(int i=2;i<=n;i++){
        int aa,bb;
        scanf("%d%d",&aa,&bb);
        ad(aa,bb);
        ad(bb,aa);//建边
    }
    for(int i=1;i<=n;i++){
        f[i]=da[i];//给每一个节点初始化价值
    }
    dfs(1,0);//从根节点开始遍历
    if(jud) printf("%d\nsolution is not unique\n",f[1]);
    //有多种情况也要输出值，不要忘了
    else printf("%d\nsolution is unique\n",f[1]);
    return 0;
}

代码的细节在注释里 这道题思维量不小，大家一定要认真思考