题目描述

给定一棵树。要求往树中加入一些边使得从1到其他节点的距离至多是2 。 输出加入边的最小数量。(边全部都是无向的)

题解:好多人都说是贪心,但是我写的是树形dp。

(这道题实在太像小胖守皇宫了)

先贪一步,每条边都由1连出,另一端距离为1。因此可以更新其父亲和儿子。

dp[ u ][ 0 / 1 / 2]:u点由自己/儿子/父亲更新。

代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 200050
int n,hed[N],cnt;
struct EG
{
int to,nxt;
}e[*N];
void ae(int f,int t)
{
e[++cnt].to = t;
e[cnt].nxt = hed[f];
hed[f] = cnt;
}
int dp[N][];
void dfs(int u,int fa)
{
dp[u][]=;
int mn = 0x3f3f3f3f,y=;
for(int j=hed[u];j;j=e[j].nxt)
{
int to = e[j].to;
if(to==fa)continue;
y=;
dfs(to,u);
dp[u][]+=min(dp[to][],min(dp[to][],dp[to][]));
dp[u][]+=min(dp[to][],dp[to][]);
dp[u][]+=min(dp[to][],dp[to][]);
if(mn>dp[to][]-dp[to][])mn=dp[to][]-dp[to][];
}
if(mn>)dp[u][]+=mn;
if(y)dp[u][]=0x3f3f3f3f;
}
int main()
{
scanf("%d",&n);
for(int f,t,i=;i<n;i++)
{
scanf("%d%d",&f,&t);
ae(f,t),ae(t,f);
}
dfs(,);
int ans = ;
for(int j=hed[];j;j=e[j].nxt)
{
int to = e[j].to;
ans+=dp[to][]-;
}
printf("%d\n",ans);
return ;
}

最新文章

  1. 远程登录linux不用输入密码的方法
  2. Python排列组合实验
  3. 解决在sublime text3在ubuntu下无法输入中文的问题
  4. 堆的 两种实现 (数组和STL)
  5. WordPress主题制作教程[壹] - 了解WP&amp;结构&amp;索引
  6. 数组-去重、排序方法、json排序
  7. C# winform xml的增删改查
  8. SQL server 表数据改变触发发送邮件
  9. 最新发布树莓派2代Wi-Fi自动连接实战(适合初学者)
  10. ubuntu14.04上实现faster rcnn_TF的demo程序及训练过程
  11. Intent 的两种主要使用方法
  12. 如何让你的传输更安全--基于SSL协议的通信模式
  13. JAVA主流日志梳理
  14. 深入理解Java虚拟机01--概述
  15. Ubuntu下pdf和图片互转
  16. 嵌入式常用技术概览之SPI
  17. 关于set_input_delay的用法分析
  18. python 读写json数据
  19. [转载]Java中的String,StringBuilder,StringBuffer三者的区别
  20. Spring Boot 容器选择 Undertow 而不是 Tomcat

热门文章

  1. 洛谷P4374 [USACO18OPEN]Disruption(树链剖分+线段树)
  2. IE6 position:fixed bug hack方式
  3. Git客户端使用教程
  4. home键拦截
  5. Volley的初步了解
  6. 等待进程结束函数中的BUG
  7. sdut1283Five in a Row, Again
  8. laravel 学习
  9. Redis相关问题收集
  10. ES之值类型以及堆和栈