首页 > 代码库 > 51Nod 1378 夹克老爷的愤怒
51Nod 1378 夹克老爷的愤怒
Description
一棵树,可以进行染色,被染色的点可以控制与它距离不超过 \(k\) 的所有点,问控制整棵树最少需要染几个点.
Sol
贪心.
记录一下最深的未染色点和最浅的染色点,判断一下能否在子树中就完成,不能的话就把权值赋成最深未染色点深度+1,能的话就赋成染色点深度+1.
需要特判一下根.
Code
#include<cstdio>#include<vector>#include<ctime>#include<cstdlib>#include<iostream>using namespace std;const int N = 100005;int n,k,ans;int f[N];vector<int> g[N];inline int in(int x=0,char ch=getchar()){ while(ch>‘9‘ || ch<‘0‘) ch=getchar(); while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();return x; }void DFS(int u,int fa){ int mx=0,mi=0; for(int i=0,v;i<g[u].size();i++) if((v=g[u][i])!=fa){ DFS(v,u); mx=max(mx,f[v]),mi=min(mi,f[v]); } if(mx+1 > k) f[u]=-k,ans++; else if(mx+mi+1>0) f[u]=mx+1; else f[u]=mi+1;}int main(){ n=in(),k=in(); for(int i=1,u,v;i<n;i++) u=in()+1,v=in()+1,g[u].push_back(v),g[v].push_back(u); DFS(1,-1); if(f[1]>0) ans++; cout<<ans<<endl; return 0;}
51Nod 1378 夹克老爷的愤怒
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。