cf contest551 D 树上dp

Serval and Rooted Tree

题目链接

题目大意

给一棵有根树，设有k个叶子节点，给所有的叶子节点标号1~k；然后每个非叶子节点都有一个得到当前节点标号的方法，就是取他的所有子节点的最大值或最小值（取决于输入）；问根节点能得到的最大的标号是啥。

刚开始不会做，想着贪心可不可以做，于是想了半天，啥求都不会

于是瞅了一眼题解，dp做，向来不怎么dp的我很是懵逼，还是不知道怎么dp，于是又看了看，如下：
dp[i] 表示第i个节点的标号是他所有子节点标号中的第几大，也就是1~k中比它大的数至少有dp[i] - 1个
于是
叶子结点的dp值就是1。
如果操作是得到子节点的最大值，那么当前的dp值就等于子节点的dp值之和。
如果操作是得到子节点的最大值，那么当前的dp值就等于子节点的dp值的最小值，为什么是最小值？因为要是当前节点的值最大，比当前节点大的数越少越好，所以是最小值。
害~ 把maxn看错还re了一发。
代码:
这个代码其实dfs里不用fa标记的，因为题目给出树的时候直接给的是它的父亲节点是谁，并且是个有根树，所以就建单向边就好，并没有当前节点到父节点的边。

#include
#include
#include
#include
using namespace std;
const int maxn = 3e5+5;
vector<int> vv[maxn];
int dp[maxn];
int a[maxn];
int s =0 ;
void dfs(int x,int fa)
{int sum = 0;int f = 0;int maxx = maxn;for(int i = 0; i < vv[x].size(); i ++ ){int v = vv[x][i];if(v == fa)continue;f = 1;dfs(v,x);sum += dp[v];maxx = min(maxx, dp[v]);}if(f == 0){s ++ ;dp[x] = 1;}else if(a[x] == 1){dp[x] = maxx;}elsedp[x] = sum;
//	printf("%d %d\n",x,dp[x]);
}int main()
{int n;scanf("%d",&n);for (int i = 1; i <= n; i ++ ){scanf("%d",&a[i]);}for (int i = 2; i <= n; i ++ ){int x;scanf("%d",&x);vv[x].push_back(i);}dfs(1,0);
//	printf("%d\n",s);printf("%d\n",s - dp[1] + 1);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！