题目大意： 给定一棵根节点为1的带边权的树。 每次给定一些点，求把这些点与树根断开的最小花费。 题目分析： 我们可以O（n）处理出每个点与根断开的最小花费，即该节点到根的路径上的最小边权。 然后我们对于每一个询问，可以把询问的点打上标记，然后可以O（n）动态规划求解。 但是O（n）的时间复杂度接受不了，而且我们发现每次询问并不会询问所有的点，而且询问的总点数不超过50w。 这样我们可

虚树入门 题目传送门 虚树的主要思想就是对于一棵树，仅仅保留有用的点，重新构建一棵树。 #include<bits/stdc++.h>#define il inline#define pb push_back#define ms(_data,v) memset(_data,v,sizeof(_data))#define SZ(a) int((a).size())using name

Description 在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望

传送门 http://www.lydsy.com/JudgeOnline/problem.php?id=2286 题目大意 给定一棵树，树上有边权，切断一条边消耗边权大小的能量 每次给定一些关键点，使这些关键点都不能与1联通，询问最小代价 题解 树形DP dp[i]:使i不与它子树中任意一个关键点联通的最小代价 dp[i]:使i不与它子树中任意一个关键点联通的最小代价 dp[i