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

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

卡点：无

 

C++ Code：

#include 
     
      #include 
      
       #define maxn 100010const 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
       
         (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;}