首页 > 其他分享 >luogu 3155

luogu 3155

时间:2022-11-03 23:55:28浏览次数:53  
标签:int luogu 着色 add 3155 go 节点 hd

 m 个节点的无根树,选一个根,将一些节点 染成黑色或白色。你的着色方案应保证根节点到各叶子节点的简单路径上都包含一个有色节点,哪怕是叶子本身。

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

 

#include <bits/stdc++.h>
using namespace std ;
  const int N=1e4+2,M=5*N;
 int n,m,a[N],f[N][2],nxt[M],go[M],all,hd[N];
 void add(int x,int y){
     go[++all]=y; nxt[all]=hd[x],hd[x]=all;
 }
 void dfs(int x,int fa){
     if(x<=m) return ;
     
     int i,y;
     for(i=hd[x];i;i=nxt[i]){
         y=go[i]; if(fa==y) continue;
         dfs(y,x);
         
         f[x][0]+=min(f[y][0]-1,f[y][1]);
         f[x][1]+=min(f[y][1]-1,f[y][0]);
     }
 }
 int main(){
     int i,x,y; 
     memset(f,0x7f7f3f,sizeof(f));
       cin>>n>>m;
    for(i=1;i<=m;i++) cin>>x,f[i][x]=1;
    
    for(i=1;i<n;i++) {
      cin>>x>>y,add(x,y),add(y,x);
      if(i>m) f[i][0]=f[i][1]=1; 
    }
    f[n][0]=f[n][1]=1;
    dfs(n,0);
    cout<<min(f[n][0],f[n][1]);
 }
 
 
 

 

标签:int,luogu,着色,add,3155,go,节点,hd
From: https://www.cnblogs.com/towboa/p/16856316.html

相关文章

  • Luogu P5435 基于值域预处理的快速 GCD
    最近做这道题的时候被卡常了,然后突然想起来曾经偶然在陈指导的博客看到过这个\(O(1)\)做\(\gcd\)的方法其实理解了之后还是比较简单的,以下设数的值域为\(S\)首先我们定义......
  • Luogu4315 月下“毛景树” - 树链剖分 -
    题目链接:https://www.luogu.com.cn/problem/P4315题意:一棵有边权的树,维护树上的链加、链覆盖、修改边权、链上max题解:好难写...首先把边权转化为儿子的点权然后树链剖......
  • 【luogu P1600】天天爱跑步(线段树合并)(LCA)
    天天爱跑步题目链接:luoguP1600题目大意有一棵树,给你若干条路径,对于每个点,有一个数x,求出有多少条路径的第x个点是当前点。思路考虑把路径拆成两个部分,向上和向下。......
  • 【XSY2444】【BZOJ4042】【CERC2014】【luogu4757】Parades(树形dp+状压dp)
    题面Description从前有个A国,它有\(n\)个城市和\(n-1\)条道路。每条路连接两个城市。城市之间两两可达。每个城市与不超过10条道路相连。现在给出\(m\)条路径,要求从这些......
  • luogu 1908 逆序对板子
     逆序对的本质是二维偏序 给第一维排序(输入时已排好),统计y(k)>=y(i)k<i的个数用树状数组维护y值前缀和,需要的时候直接查询该题需要离散化这个y,再作为树状数组......
  • luogu 4588
    给xx这个数进行操作1m:将 xx 变为x,并输出 x%mod2pos:将 xx 变为 xx 除以第 pos 次操作所乘的数(保证第 pos 次操作一定为类型1,对于每一个类型1的操作至多......
  • Luogu P5658 括号树
    LuoguP5658括号树来补一道当年考场上没做出来的题。不难想到树上DP,关键在于如何设置函数与转移。按题意,记$k_i$为以$s_i$结尾的串中的合法子串数;记$cnt_i$为......
  • 【luogu P6130】随机红包(数学)(期望)
    随机红包题目链接:luoguP6130题目大意把一个数1分成n份,求第k小的期望大小,多次询问。思路首先考虑最小的期望大小,那假设最小的是\(x\),剩下的都大于\(x\)。那......
  • Luogu 2894 酒店Hotel
    题目链接:​​传送门​​题目描述:参考样例,第一行输入n(1≤n≤50,000),m(1≤M<50,000),n代表有n个房间,编号为1—n,开始都为空房,m表示以下有m行操作,以下每行先输入一个......
  • Luogu 3478 [POI2008]STA-Station
    题目链接:​​传送门​​题目描述给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大输入样例814564567682434输出样例7一句话题意好......