题意:给出一棵树,带有向边,找出某个点到达所有点需要反转的最少的边。

解题关键:和求树的直径的思路差不多,将求(父树-子树)的最大值改为求特定值。依然是两次dfs,套路解法。

对树形dp的理解:树形dp其实就是将树进行暴力搜索,只是需要理解状态的概念。那些状态已经完成,需要从底还是从顶开始搜索。

 #include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=1e6+;
const int inf=0x3f3f3f3f;
int head[maxn],tot,n,m,sum;
int dp[maxn][],cnt[maxn];
struct edge{
int to;
int nxt;
int w;
}e[maxn<<];
void add_edge(int u,int v,int w){
e[tot].to=v;
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot++;
} void dfs1(int u,int fa){
for(int i=head[u];i!=-;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
dfs1(v,u);
dp[u][]+=dp[v][]+e[i].w;
}
} void dfs2(int u,int fa){
for(int i=head[u];i!=-;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
dp[v][]=dp[u][]-dp[v][]+dp[u][];
if(e[i].w==) dp[v][]+=;
else dp[v][]-=;
dfs2(v,u);
}
} inline int read(){
char k=;char ls;ls=getchar();for(;ls<''||ls>'';k=ls,ls=getchar());
int x=;for(;ls>=''&&ls<='';ls=getchar())x=(x<<)+(x<<)+ls-'';
if(k=='-')x=-x;return x;
} int main(){
int k=;
while(scanf("%d",&n)!=EOF){
memset(head,-,sizeof head);
tot=;
int a,b;
/*for(int i=1;i<n;i++){
cnt[i]=read();
sum+=1ll*cnt[i];
}*/
for(int i=;i<n-;i++){
a=read();
b=read();
add_edge(a,b,);
add_edge(b,a,);
}
dfs1(,-);
dfs2(,-);
for(int i=;i<=n;i++){
dp[i][]=dp[i][]+dp[i][];
}
int min1=inf;
for(int i=;i<=n;i++){
min1=min(dp[i][],min1);
}
cout<<min1<<"\n";
for(int i=;i<=n;i++){
// cout<<dp[i][2]<<" ";
if(dp[i][]==min1) cout<<i<<" ";
}
}
return ;
return ;
}

最新文章

  1. ubuntu15.04 nginx1.6.5 配置虚拟主机
  2. 51nod1130(斯特林近似)
  3. 关于ellipsis多行换行的方案
  4. uva 12034
  5. ie6兼容之绝对定位元素内容为空时高度问题
  6. SharePoint 页面中添加.Net代码
  7. WCF服务通过防火墙怎么设置
  8. (高精度运算4.7.27)UVA 10494 If We Were a Child Again(大数除法&amp;&amp;大数取余)
  9. javascript 不间断向左滚动图片
  10. 补间动画 Interpolator 简介 示例
  11. contentSize、contentInset和contentOffset
  12. 切换tab,并且动态添加标签
  13. 笔记:查看linux系统开机时间
  14. Kafka 源代码分析之ByteBufferMessageSet
  15. 造轮子-Java泛型堆排
  16. 基于微服务的DevOps落地指南 交付效率提升40%
  17. mysql数据库可以远程连接或者说用IP地址可以访问
  18. 解决OS睡眠功能中,移动鼠标就会唤醒
  19. Ant压缩与解压缩
  20. Linux 套接字与文件描述符

热门文章

  1. asp.net 后台多线程异步处理时的 进度条实现一(Ajax+Ashx实现以及封装成控件的实现)
  2. 【转】iOS安全之RSA加密/生成公钥、秘钥 pem文件
  3. YII框架学习(一)
  4. 文件查找工具Everything小工具的使用
  5. ORACLE DATABASE 10g EXPRESS EDITION LICENSE AGREEMENT
  6. Nginx Cache中$request_filename(转)
  7. opencv轮廓提取、轮廓识别相关要点
  8. 【docker】kubernetes集群一键部署包
  9. iOS MVVM+RAC 从基础到demo
  10. debian7 amd64版本添加对x86包的支持