[洛谷P3931]SAC E#1 - 一道难题 Tree

谁借莪１个温暖的怀抱￠ 2021-12-22 04:17 104阅读 0赞

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

**题解：**做了一天的网络流，这道题显然可以用最小割来做，但是也可以用树形$DP$，基本同[\[SDOI2011\]消耗战][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;
    }

转载于:https://www.cnblogs.com/Memory-of-winter/p/10342942.html

[SDOI2011]: https://www.cnblogs.com/Memory-of-winter/p/10184109.html

发表评论取消回复

表情：

评论列表（有 0 条评论，104人围观）

还没有评论，来说两句吧...

相关阅读

相关洛谷P3806 【模板】点分治1

【模板】点分治1 [题目传送门][Link 1] 代码如下 include <bits/stdc++.h> define INF 0x3f3f3f3f u

秒速五厘米/ 2023年08月17日 17:21/ 0 赞/ 143 阅读

相关洛谷P3690 【模板】Link Cut Tree （动态树）

【模板】Link Cut Tree （动态树） [题目传送门][Link 1] 解题思路妈妈我终于学会LCT了。代码如下 include <b

Love The Way You Lie/ 2023年08月17日 17:21/ 0 赞/ 84 阅读

相关 P3372 【模板】线段树 1---洛谷

题目描述题目描述如题，已知一个数列，你需要进行下面两种操作： 1.将某区间每一个数加上 k。 2.求出某区间每一个数的和。输入格式第一行包含两

r囧r小猫/ 2023年07月17日 11:28/ 0 赞/ 40 阅读

相关洛谷p1164

> P1164 小A点菜 > > 题目描述 > > uim口袋里有剩M元（M<=10000）。 > > 餐馆虽低端，但是菜品种类不少，有N种（N<=100），第i

亦凉/ 2022年06月09日 01:53/ 0 赞/ 358 阅读

相关洛谷 P3382

题目：[点击打开链接][Link 1] 题意：如题，给出一个N次函数，保证在范围\[l,r\]内存在一点x，使得\[l,x\]上单调增，\[x,r\]上单调减。试求出x

绝地灬酷狼/ 2022年05月14日 00:19/ 0 赞/ 356 阅读

相关洛谷P1540——机器翻译

题目背景小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。题目描述这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义

傷城~/ 2022年04月14日 06:55/ 0 赞/ 336 阅读

相关洛谷P1002题解

include<iostream> using namespace std; long long a[30][30]={0},n,m,my,m

我会带着你远行/ 2022年03月19日 04:16/ 0 赞/ 388 阅读

相关 [洛谷P3931]SAC E#1 - 一道难题 Tree

题目大意：给你一棵带权有根树，可以切断一些边，问使得根和叶子节点不连通的最小代价。题解：做了一天的网络流，这道题显然可以用最小割来做，但是也可以用树形$DP$，基本同[\[

谁借莪１个温暖的怀抱￠/ 2021年12月22日 04:17/ 0 赞/ 105 阅读

相关洛谷P3690 Link Cut Tree（LCT）

题意：给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。 0：后接两个整数(x，y)，代表询问从x到y的路径上

水深无声/ 2021年11月09日 10:54/ 0 赞/ 168 阅读

相关洛谷 P4961

目录题目思路 Code 题目 [戳][Link 1] 为了小埋A了这道题。思路读入原来的矩阵，将不是雷的格子更新为数字（数字就是

左手的ㄟ右手/ 2021年10月26日 20:28/ 0 赞/ 482 阅读