#树形dp#jzoj 1010 洛谷 3155 叶子的颜色

news/2024/2/28 0:14:21

题目

对于每个叶结点u,定义c[u]为从u到根结点的简单路径上第一个有色结点的颜色。给出每个c[u]的值,设计着色方案,使得着色结点的个数尽量少。


分析

这道题可以用树形dp, f [ x ] [ 0 / 1 ] f[x][0/1] f[x][0/1]表示x点不着色/着色的最小着色结点个数,
容易得到 f [ x ] [ 0 ] = ∑ m i n ( f [ s o n ] [ 0 ] − 1 , f [ s o n ] [ 1 ] ) f[x][0]=\sum min(f[son][0]-1,f[son][1]) f[x][0]=min(f[son][0]1,f[son][1])
f [ x ] [ 1 ] = ∑ m i n ( f [ s o n ] [ 0 ] , f [ s o n ] [ 1 ] − 1 ) f[x][1]=\sum min(f[son][0],f[son][1]-1) f[x][1]=min(f[son][0],f[son][1]1)
初始化时,对于每个叶子节点着色为1,不着色inf,而根节点初始化都是1。


代码

#include <cstdio>
#include <cctype>
#define min(a,b) (a<b)?a:b
using namespace std;
struct node{int y,next;}e[200001];
int n,m,ques[100001],ls[100001],f[200001][2];
int in(){int ans=0; char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
void dp(int x,int fa){if (x<=n) f[x][ques[x]]=1,f[x][ques[x]^1]=1<<23; else f[x][0]=f[x][1]=1;for (int i=ls[x];i;i=e[i].next){if (e[i].y==fa) continue;dp(e[i].y,x);f[x][0]+=min(f[e[i].y][0]-1,f[e[i].y][1]);f[x][1]+=min(f[e[i].y][0],f[e[i].y][1]-1);}
}
int main(){m=in(); n=in();for (int i=1;i<=n;i++) ques[i]=in();for (int i=1,x,y;i<m;i++){x=in(); y=in();e[i]=(node){y,ls[x]}; ls[x]=i;e[i+m]=(node){x,ls[y]}; ls[y]=i+m;}dp(m,0); return !printf("%d",min(f[m][0],f[m][1]));
}

http://www.ppmy.cn/news/405951.html

相关文章

BZOJ3155 Preprefix sum

一个数相当于给他后边的前缀和序列加了一个等差数列 直接线段树 #include<iostream> #include<cstdlib> #include<cstdio> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<iomanip> #incl…

Hard Life poj3155

最大密度子图&#xff0c;论文题目。 这题构造出来的g(k) max{∑E-k∑V},g(k)是一个下界为0的单调递减函数&#xff0c;即存在x1, g(x1) 0, 对于所有x > x1, g(x)≡0。按照论文上的证明方法的话我们只要发现一个g(k) 0,就可以认为是最 优解了&#xff0c;但是此题要二…

bzoj3155 Preprefix sum 线段树

Description Solution 只会写水题了。。 可以发现每次改a[x]就是在改[x,n]的前缀和s&#xff0c;那么线段树区间修改区间查询即可 Code #include <stdio.h> #include <string.h> #include <algorithm> #define rep(i,st,ed) for (int ist;i<ed;i) typed…

【GAOPS024】仿真pcie ip 一部分问题 ERROR: [VRFC 10-3155]

仿真报错 UG937 vivado 仿真的基本概念 xvlog/xvhdl:解析verilog/vhdl源文件&#xff0c;&将解析之后的文件存在硬盘HDL lib xelab:整理层次顺序&转化为可执行代码&链接link可执行代码快照到仿真kernel xsim:执行仿真GUI/TCL/batch 调用modelsim卡在这一步,原因…

[POJ3155]Hard Life

[POJ3155]Hard Life 试题描述 John is a Chief Executive Officer at a privately owned medium size company. The owner of the company has decided to make his son Scott a manager in the company. John fears that the owner will ultimately give CEO position to Scot…

POJ - 3155 Hard Life

传送门 一道最大密度子图的模板题 一道卡精度的神题 二分精度不能太大&#xff0c;网络流精度不能太小 &#xff08;&#xff1a; //Achen #include<algorithm> #include<iostream> #include<cstring> #include<cstdlib> #include<vector> #incl…

【JZOJ3155】最短路

description N 个结点、M 个含K 个结点的完全子图构成一个奇怪的图&#xff0c;问从结点1 走 到结点N 最少需要经过多少个结点。 analysis b f s bfs bfs 对于一个小完全图&#xff0c;不要暴力两两连边 其实我们把它连成一个菊花图&#xff0c;用中间的点连向这些点即可 然…

洛谷 P3155 [CQOI2009]叶子的染色

题目&#xff1a;叶子的染色 思路&#xff1a; 嗯首先每个节点都只有3种状态&#xff1a;白色、黑色、无色。 个人感觉选择根节点不太好处理&#xff0c;那我们先讨论假如根节点确定的情况。 我们先假设一个节点的所有儿子都有颜色&#xff0c;来看一下选择的情况。 如图…

新手第一次做性能测试?性能测试流程详全,从需求到报告一篇打通

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 1、确认需求 确定…

pink老师 js p85思考题

var str ;for (var i1; i <10; i) { //外层循环负责打印五行for (var j 1; j < i; j) { //里层循环打印的个数不一样 j1str str ★;}//如果一行打印完毕5个星星就要另起一行 加\nstr str \n;}console.log(str); 内循环中 j < 10改为j < i var str ;var nu…

P85指针和数组 #C语言的学习

一.c语言规定允许指向数组元素的指针与指向数组最后一个元素后面的那个内存位置的指针比较&#xff0c;但是不允许往数组的第一个元素之前进行比较 二.数组名是数组第一个元素的地址 三.[ ]是一个操作符&#xff0c;支持交换律arr[2]2[arr] 四.二级指针 int main(){ int a…

谷粒商城P85问题记录—发布商品时规格参数不显示-2022/4/8

谷粒商城P85问题记录—发布商品时规格参数不显示 这一p有2个问题&#xff0c;折腾了很久 问题1 &#xff1a;数据库表中不存在 valueType这个键 但是接口文档里是需要提供这个键&#xff08;而且是不能为null&#xff09; 所以需要&#xff1a; 1、在数据库表pms_attr添加va…

P85程序出错的处理机制

3.定义条件和处理程序 3.1错误演示 #2.1错误演示&#xff1a;#错误代码&#xff1a; 1364 #Field email doesnt have a default value INSERT INTO employees(last_name) VALUES(Tom);DESC employees;#错误演示&#xff1a;DELIMITER //CREATE PROCEDURE UpdateDataNoConditi…

自用--选择问题(P85)

寻找T的第k小元素 寻找第n/2小元素--》中值问题 ks rs就是第k小元素 k<s rs在左边序列中 k>s rs在右边序列中 #include<iostream> using namespace std;int Partition(int r[],int low,int high){//对数据进行划分 //无序数组 左边 右边 左小右大int ilow,jhigh…

C语言进阶--指针(C语言灵魂)

目录 1.字符指针 2.指针数组 3.数组指针 4.数组参数与指针参数 4.1.一维数组传参 4.2.二维数组传参 4.3.一级指针传参 4.4.二级指针传参 5.函数指针 6.函数指针数组 7.指向函数指针数组的指针 8.回调函数 qsort函数 9.指针和数组笔试题 10.指针笔试题 前期要点回…

谷粒商城P85单选和多选无法修改问题

谷粒商城P85单选和多选无法修改问题 问题&#xff1a;数据库表中不存在 value_Type这个字段 接口文档里是需要提供value_Type这个键&#xff08;而且是不能为null&#xff09;解决方法&#xff1a; 1、在数据库表pms_attr添加value_type字段&#xff0c;类型为tinyint&#x…

谷粒商城P85页面不显示

一开始报错如下&#xff1a; Cannot read properties of null (reading forEach)原因是返回的属性分组没有关联属性&#xff0c;即attrs: null&#xff0c;所以遍历失败 评论区说可以在前端检查&#xff0c;我试了一下还是报错如下 "TypeError: Cannot read properties …

P85-前端基础动画效果-动画缩放效果

P85-前端基础动画效果-动画缩放效果 1.概述 这篇文章介绍动画缩放效果 对元素进行缩放的函数&#xff1a; scaleX() 水平方向缩放scaleY() 垂直方向缩放scaleZ() Z方向缩放scale() 双方向的缩放 2.缩放 2.1.缩放代码 <!DOCTYPE html> <html><head><met…
最新文章