[codeforces219D]Choosing Capital for Treeland树形dp
2024-08-29 10:23:14
题意:给出一棵树,带有向边,找出某个点到达所有点需要反转的最少的边。
解题关键:和求树的直径的思路差不多,将求(父树-子树)的最大值改为求特定值。依然是两次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 ;
}
最新文章
- ubuntu15.04 nginx1.6.5 配置虚拟主机
- 51nod1130(斯特林近似)
- 关于ellipsis多行换行的方案
- uva 12034
- ie6兼容之绝对定位元素内容为空时高度问题
- SharePoint 页面中添加.Net代码
- WCF服务通过防火墙怎么设置
- (高精度运算4.7.27)UVA 10494 If We Were a Child Again(大数除法&;&;大数取余)
- javascript 不间断向左滚动图片
- 补间动画 Interpolator 简介 示例
- contentSize、contentInset和contentOffset
- 切换tab,并且动态添加标签
- 笔记:查看linux系统开机时间
- Kafka 源代码分析之ByteBufferMessageSet
- 造轮子-Java泛型堆排
- 基于微服务的DevOps落地指南 交付效率提升40%
- mysql数据库可以远程连接或者说用IP地址可以访问
- 解决OS睡眠功能中,移动鼠标就会唤醒
- Ant压缩与解压缩
- Linux 套接字与文件描述符
热门文章
- asp.net 后台多线程异步处理时的 进度条实现一(Ajax+Ashx实现以及封装成控件的实现)
- 【转】iOS安全之RSA加密/生成公钥、秘钥 pem文件
- YII框架学习(一)
- 文件查找工具Everything小工具的使用
- ORACLE DATABASE 10g EXPRESS EDITION LICENSE AGREEMENT
- Nginx Cache中$request_filename(转)
- opencv轮廓提取、轮廓识别相关要点
- 【docker】kubernetes集群一键部署包
- iOS MVVM+RAC 从基础到demo
- debian7 amd64版本添加对x86包的支持