标签：实现   har   没有   模拟   char   pre   问题   name   ace   

题目链接 https://www.luogu.com.cn/problem/P6082

分析

这题一眼应该就能看出来是树形DP，题目中都多次暗示了，所以先把定义搞出来，最开始我跳了一个坑就是把状态定义成了\(DP[i][j]\)，即在\(i\)号节点停留\(j\)次的最大收益，然后想啊想，就没有然后了。。。。。
模拟几个样例发现停留次数有一个很特殊的性质，就是最多只能经过该点的儿子停留次数-1次，不然就回不了家了，但好像对我们这个转移没有什么帮助，回去读一遍题，发现点权可能为负？负的？那第二维状态就没意义了，我要是那个\(Salesman\)，肯定先去赚钱多的，不去亏本的，所以这好像直接用一个贪心就可以了，证明也比较好证吧，去一个权大的点肯定比去一个权小的点收获大，不去负权点肯定比去收获大，所以每次从大到小取够停留次数减一或把正儿子取完即可，所以转移方程就是\(DP[u]=\sum_{i=1}^s{DP[i]}\)
下面考虑第二个问题，多组解，因为这是个树，所以只有两种情况有多组解，一是有一个子树的权值为0，这样不管怎么走都可以，另一个是所选的最后一棵子树与一棵未选的子树权值一样，这样我们完全可以选另外一棵子树。关于选子树的话，我用的是堆，这个判断是不是为空啊什么的比较方便，当然用\(sort\)也行，然后就是代码实现啦，其实想明白也挺简单。

#include
#include
#include
using namespace std;
const int N=1e5+10;
struct Edge{
    int to,nxt;
}e[N‘9‘){
        if(ch==‘-‘)w=-1;ch=getchar();
    }
    while(ch=‘0‘){
        x=x*10+ch-‘0‘;
        ch=getchar();
    }
    return x*w;
}
void dfs(int u,int fa){
    priority_queue q;
    dp[u]=w[u];
    for(int i=Head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa)continue;
        dfs(v,u);
        q.push(Node(dp[v],g[v]));
    }
    int tot=1,last;
    while(++tot

JSOI Salesman 树形Dp

标签：实现   har   没有   模拟   char   pre   问题   name   ace   

原文地址：https://www.cnblogs.com/anyixing-fly/p/12633625.html