loj10161 叶子的颜色
2024-08-29 11:04:31
CQOI 2009
给一棵有 mm 个节点的无根树,你可以选择一个度数大于 11 的节点作为根,然后给一些节点(根、内部节点、叶子均可)着以黑色或白色。你的着色方案应保证根节点到各叶子节点的简单路径上都包含一个有色节点,哪怕是叶子本身。
对于每个叶子节点 uu,定义 c_ucu 为从根节点到 uu 的简单路径上最后一个有色节点的颜色。给出每个 c_ucu 的值,设计着色方案使得着色节点的个数尽量少。
输入格式
第一行包括两个数 m,nm,n,依次表示节点总数和叶子个数,节点编号依次为 11 至 mm。
接下来 nn 行每行一个 00 或 11 的数,其中 00 表示黑色,11 表示白色,依次为 c_1,c_2,\cdots ,c_nc1,c2,⋯,cn 的值。
接下来 m-1m−1 行每行两个整数 a,ba,b,表示节点 aa 与 bb 有边相连。
输出格式
输出仅一个数,表示着色节点数的最小值。
样例
样例输入
5 3
0
1
0
1 4
2 5
4 5
3 5
样例输出
2
——————————————————————————————————————————————————————
树形动归
f[u][0]表示u点染成白色时总共要染多少个点
f[u][1]表示u点染成黑色时总共要染多少个点
f[u][0]=sum( min( f[v][0]-1,f[v][1] ) )+1
f[u][1]=sum( min( f[v][1]-1,f[v][0] ) )+1
——————————————————————————————————————————————————————
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn=10010;
4 int n,m;
5 int tj[maxn][2];
6 struct edge
7 {
8 int u,v,nxt;
9 }e[maxn<<1];
10 int head[maxn],js;
11 void addage(int u,int v)
12 {
13 e[++js].u=u;e[js].v=v;
14 e[js].nxt=head[u];head[u]=js;
15 }
16 void dfs(int u,int fa)
17 {
18 for(int i=head[u];i;i=e[i].nxt)
19 {
20 int v=e[i].v;
21 if(v!=fa)
22 {
23 dfs(v,u);
24 tj[u][0]+=min(tj[v][0]-1,tj[v][1]);
25 tj[u][1]+=min(tj[v][1]-1,tj[v][0]);
26 }
27 }
28 }
29 int main()
30 {
31 scanf("%d%d",&m,&n);
32 for(int x,i=1;i<=n;++i)
33 {
34 scanf("%d",&x);
35 tj[i][x]=1;
36 tj[i][x^1]=10000000;
37 }
38 for(int i=n+1;i<=m;++i)tj[i][0]=tj[i][1]=1;
39 for(int u,v,i=1;i<m;++i)
40 {
41 scanf("%d%d",&u,&v);
42 addage(u,v);addage(v,u);
43 }
44 dfs(m,0);
45 cout<<min(tj[m][0],tj[m][1]);
46 return 0;
47 }
最新文章
- Android源码编译make的错误处理
- Linux文件锁flock
- 响应式设计,bootstrap框架的IE兼容问题
- mysql 数据类型,字符集
- Visual Studio + SqlServer
- oracle 10G以上版本 树形查询新加的几个功能
- 【实验室笔记】C#以本地时间创建txt文件
- MYSQL中的多类型查询及高级查询操作
- bootloader总体操作设计
- 大数据 -->; Spark与Hadoop对比
- HDFS APPEND性能测试
- mybatis 一对多查询
- axios与ajax区别
- 2018-2019-2 20165308网络对抗技术 Exp6:信息收集与漏洞扫描
- psnr的定义和python实现
- 查找所有sphinx引擎表并生成创建表的语句
- day29 上周复习
- Diamorphine rootkit的使用
- 原生JavaScript实现新手引导效果(第二个玩具)
- C#使用七牛云存储上传下载文件、自定义回调