题意：
一棵有n个点的树，树上有m个障碍在给定的位置，现在需要移动这m个障碍，使得从根节点出发的任意路径不能到达任意一个叶子节点（不能放在根节点上），求移动的最小花费。
题解：
首先需要明白的有这几点：
① 如果一个点所有的儿子都被阻碍了，那么这个点也会被阻碍，那么现在的问题就是覆盖根所有的儿子节点。
② 若在规定的时间移动这m个点，那么这m个点越往上移动越优越。
③ 若在规定的时间移动这m个点，那么一定会出现两种情况，第一种不能越过根节点，第二种能够越过根节点。
现在需要解决一下问题：
1.怎么解决规定的时间，可以二分一个时间。
2.怎么在很小的复杂度使得m个点尽量的往上跳，倍增
3.怎么处理那两种情况？
首先处理不能越过根节点的情况，尽量的往上跳，把到达极限的点标记，然后将所有的标记根据①的原理上传到根的儿子。
然后处理能够越过根节点的情况，记录下每个能够越过根节点的点剩余的时间 t 和属于哪条路径的根的儿子的编号 id，记录下需要被其他路径的点覆盖的根的儿子的编号，然后贪心覆盖就好了。。。
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5e4 + 7;
struct edge {int v, nxt, w;}e[N<<1];
struct node {int w, id;} g[N], f[N];
int anc[20][N], cos[20][N], ecnt, head[N], vis[N], n, m, army[N];
void adde (int u, int v, int w) {
e[ecnt].v = v;
e[ecnt].w = w;
e[ecnt].nxt = head[u];
head[u] = ecnt++;
}
void DFS (int u, int pre) {
for (int it = head[u]; it != -1; it = e[it].nxt) {
int v = e[it].v;
if (v == pre) continue;
anc[0][v] = u;
cos[0][v] = e[it].w;
for (int i = 1; i <= 18; ++i) {
anc[i][v] = anc[i-1][anc[i-1][v]];
cos[i][v] = cos[i-1][v] + cos[i-1][anc[i-1][v]];
}
DFS(v, u);
}
}
bool cmp (node a, node b) {return a.w < b.w;}
void pushup (int u, int pre) {
int isleaf = 1, flag = 1;
for (int it = head[u]; it != -1; it = e[it].nxt) {
int v = e[it].v;
if (v == pre) continue;
pushup(v, u);
if (!vis[v]) flag = 0;
isleaf = 0;
}
if (flag && !isleaf && u != 1) vis[u] = 1;
}
int check (int x) {
int cntg = 0, cntf = 0;
memset (vis, 0, sizeof vis);
for (int i = 1; i <= m; ++i) {
int p = army[i], t = x;
for (int j = 18; j >= 0; --j) {
if (anc[j][p] && t >= cos[j][p]) {
t -= cos[j][p];
p = anc[j][p];
}
}
if (p == 1) {
p = army[i];
for (int j = 18; j >= 0; --j)
if (anc[j][p] > 1) p = anc[j][p];
g[++cntg] = (node){t, p};
}
else vis[p] = 1;
}
pushup(1, 0);
for (int it = head[1]; it != -1; it = e[it].nxt) {
int v = e[it].v;
if (!vis[v]) f[++cntf] = (node){e[it].w, v};
}
sort (g + 1, g + 1 + cntg, cmp);
sort (f + 1, f + 1 + cntf, cmp);
int cur = 1;
f[cntf+1] = (node){1e9 + 7, 0};
for (int i = 1; i <= cntg; ++i) {
if (!vis[g[i].id]) vis[g[i].id] = 1;
else if (g[i].w >= f[cur].w) vis[f[cur].id] = 1;
while (vis[f[cur].id]) cur++;
}
return cur > cntf;
}
int main () {
memset (head, -1, sizeof head);
scanf ("%d", &n);
for (int i = 1; i < n; ++i) {
int u, v, w;
scanf ("%d%d%d", &u, &v, &w);
adde (u, v, w);
adde (v, u, w);
}
DFS (1, 0);
scanf ("%d", &m);
for (int i = 1; i <= m; ++i) scanf ("%d", &army[i]);
int l = 0, r = 1e9 + 7;
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
if (l == 1e9 + 7) puts("-1");
else printf ("%d
", l);
return 0;
}
总结：
遇到问题不要慌张~慢慢分析，首先不要考虑复杂度，直接嘴炮，然后慢慢进行算法上的优化。。。