这个题以前写过一遍，现在再来写，感觉以前感觉特别不好写的细节现在好些多了，还是有进步吧。
这个题的核心思想就是贪心+二分。因为要求最小时间，直接来求问题将会变得十分麻烦，但是如果转换为二分答案来判断可行性，问题就会简化许多。
至于贪心的话，很容易发现每个点尽量往上面跳是最优的，这里向上跳的话我们用倍增来搞就是了。但题目中有个限制条件就是：根结点不能驻扎军队！！。那么我们就可以先让所有点尽量往上面跳，最多跳到 \(deep[x]=2\) 的位置。之后考虑题目中的限制条件怎么解决。
比较直接的想法就是所有点都跳到根节点，然后贪心进行“分配”。但这里有个问题，有些点跳到根节点回不来怎么办?那么此时我们就可以大胆猜想：留住一个回不去的深度为2的结点，其余点就像之前那样贪心进行分配。
为什么这样是对的，给出一个简略证明：
如果一个点 \(x\) 跳到根节点但无法回去，此时另外一个点 \(y\) 来管辖 \(x\) 之前的所在的子树， \(x\) 现在可能去管辖另外一个以 \(z\) 为根节点的子树，满足 \(dis(z,root)<dis(x,root)\) 。我们很容易知道， \(y\) 肯定也能去管辖 \(z\) 所在子树的。因为 \(y\) 能够移动的距离更长，所以 \(y\) 对于 \(x\) 有更多的可能性(前途更加光明)
因此可以知道我们的贪心策略不会使答案变差的，那思路就是这样了。
至于代码细节，首先第一次dfs预处理出倍增的信息，之后二分进行check，里面嵌套一个dfs求出哪些深度为2的结点留住了军队。最后其余的点贪心去分配就行了。中途维护的信息可能有点多，多开几个数组维护一下= =。
代码如下(自认为比较好懂)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 50005;
int n, m;
int a[N], c[N];
int f[N][20], deep[N] ;
ll dis[N][20];
struct Edge{
int v, next, w;
}e[N << 1];
struct Army{
int id;
ll res;
bool operator < (const Army &A)const {
return res < A.res ;
}
}b[N], d[N], k[N];
int head[N], tot;
void adde(int u, int v, int w) {
e[tot].v = v; e[tot].w = w; e[tot].next = head[u]; head[u] = tot++;
}
void dfs1(int u, int fa) {
deep[u] = deep[fa] + 1;
for(int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if(v == fa) continue ;
dis[v][0] = e[i].w;
f[v][0] = u;
for(int j = 1; j <= 17; j++) {
f[v][j] = f[f[v][j - 1]][j - 1] ;
dis[v][j] = dis[v][j - 1] + dis[f[v][j - 1]][j - 1] ;
}
dfs1(v, u) ;
}
}
bool vis[N] ;
vector <int> node[N];
int cnt, num;
bool dfs2(int u, int fa) {
int sz = node[u].size();
bool ok = 1, in = 0;
for(int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if(v == fa) continue ;
in = 1;
if(!dfs2(v, u)) ok = 0;
}
if(!in) ok = 0;
if(deep[u] == 2 && ok) vis[u] = 1;
if(deep[u] == 2 && sz) {
int st = 0;
if(!vis[u] && b[node[u][0]].res < 2 * dis[u][0]) st++, vis[u] = 1;
for(int i = st; i < sz; i++) {
d[++cnt].id = b[node[u][i]].id;
d[cnt].res = b[node[u][i]].res;
}
}
return ok || sz;
}
bool check(ll x) {
for(int i = 1; i <= n; i++) node[i].clear(), vis[i] = 0;
for(int i = 1; i <= m; i++) b[i].id = a[i] ;
for(int i = 1; i <= m; i++) {
ll res = x;
int now = b[i].id;
for(int j = 17; j >= 0; j--) {
if(deep[f[now][j]] >= 2 && dis[now][j] <= res) {
res -= dis[now][j] ;
now = f[now][j] ;
}
}
b[i].id = now; b[i].res = res ;
}
num = cnt = 0;
sort(b + 1, b + m + 1);
for(int i = 1; i <= m; i++) node[b[i].id].push_back(i) ;
dfs2(1, 0) ;
for(int i = 1; i <= n; i++)
if(deep[i] == 2 && !vis[i])
k[++num].res = dis[i][0], k[num].id = i;
for(int i = 1; i <= cnt; i++) {
int now = d[i].id ;
if(dis[now][0] < d[i].res) d[i].res -= dis[now][0];
else d[i].res = 0;
}
sort(d + 1, d + cnt + 1) ;
sort(k + 1, k + num + 1) ;
if(cnt < num) return false;
for(int i = 1, j = 1; i <= cnt; i++) {
if(d[i].res >= k[j].res) {
vis[k[j].id] = 1;
j++;
}
}
bool ok = 1;
for(int i = 1; i <= n; i++)
if(deep[i] == 2 && !vis[i]) ok = 0;
return ok;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0) ;
cin >> n;
memset(head, -1, sizeof(head)) ;
ll l = 0, r = 0, mid;
for(int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
adde(u, v, w); adde(v, u, w) ;
r += w;
}
ll tmp = r;
dfs1(1, 0) ;
cin >> m;
for(int i = 1; i <= m; i++) cin >> a[i] ;
while(l < r) {
mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
if(l == tmp) cout << -1;
else cout << r ;
return 0;
}