CF1153D Serval and Rooted Tree（树形DP）
发布时间：2020-12-14 01:33:13 所属栏目：Linux 来源：网络整理
导读：? 题目链接： https://www.luogu.org/problemnew/show/CF1153D （cf崩了，贴了个落谷的） 题目大意：给你n个点，然后n-1条边，构成一棵树，每个点是子节点的最大值或最小值，将叶子节点填上整数（1~k，k为叶子节点的个数），使这棵树的根最大。 具体思路：对
|
? 题目链接： https://www.luogu.org/problemnew/show/CF1153D（cf崩了，贴了个落谷的） 题目大意：给你n个点，然后n-1条边，构成一棵树，每个点是子节点的最大值或最小值，将叶子节点填上整数（1~k，k为叶子节点的个数），使这棵树的根最大。 具体思路：对于每一个非叶子节点，假设他的值是x，如果这个点是取max，那么就要求这个节点的子节点中至少有一个是等于x的，其他都是小于x的。如果这个点是取min，那么就要求这个节点的子节点的值都是大于等于x的。然后再继续分析，我们把当前的节点赋值 为他的子树中叶子节点的个数，那么当这个节点为取max的时候，我们就相当于他的所有子节点中取一个最大的就可以了。也就是相当于从子树中取一个最小消耗量。当为min的时候，当前节点的消耗量为他的所有子节点的消耗量之和。然后根节点的最大数就变成了k-num[1]+1.num[1]为根节点的消耗量。 AC代码： 1 #include<bits/stdc++.h> 2 using namespace std; 3 # define inf 0x3f3f3f3f 4 # define ll long long 5 const int maxn = 3e5+100; 6 int col[maxn]; 7 vector<int>Edge[maxn]; 8 int tot=0; 9 int num[maxn]; 10 void dfs(int u) 11 { 12 if(Edge[u].size()==0) 13 { 14 15 tot++; 16 num[u]=1; 17 return ; 18 } 19 if(col[u]) 20 num[u]=inf; 21 else 22 num[u]=0; 23 for(int i=0; i<Edge[u].size(); i++) 24 { 25 int to=Edge[u][i]; 26 dfs(to); 27 if(col[u]) 28 num[u]=min(num[to],num[u]); 29 else 30 num[u]+=num[to]; 31 } 32 return ; 33 } 34 int main() 35 { 36 int n; 37 scanf("%d",&n); 38 for(int i=1; i<=n; i++) 39 scanf("%d",&col[i]); 40 int tmp; 41 for(int i=2; i<=n; i++) 42 { 43 scanf("%d",&tmp); 44 Edge[tmp].push_back(i); 45 } 46 dfs(1); 47 printf("%dn",tot-num[1]+1); 48 return 0; 49 }
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |