题目大意:给你一棵带权有根树,可以切断一些边,问使得根和叶子节点不连通的最小代价。

题解:做了一天的网络流,这道题显然可以用最小割来做,但是也可以用树形$DP$,基本同[SDOI2011]消耗战,这道题一次询问,只需要那个$O(n)$的$DP$就行了。

卡点:

C++ Code:

#include <algorithm>
#include <cstdio>
#define maxn 100010
const long long inf = 0x3f3f3f3f3f3f3f3f; int head[maxn], cnt;
struct Edge {
int to, nxt, w;
} e[maxn << 1];
inline void addedge(int a, int b, int c) {
e[++cnt] = (Edge) { b, head[a], c }; head[a] = cnt;
e[++cnt] = (Edge) { a, head[b], c }; head[b] = cnt;
} int n, rt, ind[maxn]; long long dfs(int u, int fa = 0) {
long long res = 0;
for (int i = head[u], v; i; i = e[i].nxt) {
v = e[i].to;
if (v != fa) res += std::min(dfs(v, u), static_cast<long long> (e[i].w));
}
if (u != rt && ind[u] == 1) return inf;
return res;
} int main() {
scanf("%d%d", &n, &rt);
for (int i = 1, a, b, c; i < n; ++i) {
scanf("%d%d%d", &a, &b, &c);
addedge(a, b, c);
++ind[a], ++ind[b];
}
printf("%lld\n", dfs(rt));
return 0;
}

  

最新文章

  1. myeclipse 无法启动 java.lang.IllegalStateException: Unable to acquire application service. Ensure that the org.eclipse.core.runtime bundle is resolved and started (see config.ini).
  2. 标签语义化之常用HTML标签
  3. java基础介绍(转)
  4. SQLdiag-配置文件-ProfilerCollector
  5. FileDataSource java的文件操作
  6. 【经验】Windows7、8、8.1 MSI安装错误Error Code 2502 &amp; 2503 解决方法
  7. 怎么让自己的java系统使用支付接口
  8. 微信公众账号【iOSDevTip】推出新栏目【看大牛】
  9. BZOJ 2429: [HAOI2006]聪明的猴子
  10. Linux查看密码
  11. Android逆向破解表单注册程序
  12. net core体系-1概要
  13. vue项目目录结构
  14. 如何写出健壮的Java代码
  15. Effective C++ 第二版 31)局部对象引用和函数内new的指针 32)推迟变量定义
  16. 20145322 《网络对抗》 MSF基础应用1
  17. mock 测试 MVC
  18. vi下的查找替换命令
  19. Python 编码机制
  20. JBOSS在win7环境下启动run.bat无反应

热门文章

  1. Windows Server 2008 R2 安装域
  2. Spark性能优化--数据倾斜调优与shuffle调优
  3. 2019年猪年海报PSD模板-第五部分
  4. [JSON].value( keyPath )
  5. 谜题 (Puzzle,ACM/ICPC World Finals 1993,UVa227)
  6. python程序设计——函数设计与调用
  7. 对HashMap进行排序
  8. 数据库Mysql的学习(八)-储存过程和事务和导入导出
  9. 【Linux】Face Recognition的封装
  10. Map Reduce Application(Partitioninig/Binning)