题目链接
做法
这道题显然可以二分答案。
考虑构造解。对于每个军队，当它不能到达首都时，它的深度显然越小越好。对于可以到达首都的军队，它有两种决策：退回上一个位置、去填补其他子树的最上面节点。可以用倍增维护。
考虑一种特殊数据：
5
1 2 5
1 3 2
1 4 5
4 5 1000000000
3 3 4 5
它的构造方案是 $ 5 o 5, 4 o 3, 3 o 2 $ ，答案是 $ 7 $ 。
考虑一个能到达根节点的军队（从 $ root $ 的儿子 $ x $ 来），若它的步数还能回到上一个位置（并非时光倒流），则直接将它放在根节点考虑没有影响；否则它要么去一个 $ dis(root, x) geq dis(root, y), y in son(root) $ 的地方，要么待在 $ x $ 。这部分可以用 $ multiset $ 维护。
最后贪心地从首都分配军队。
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
using namespace std;
typedef long long ll;
const int N = 300010;
int n, m, cnt[N],fa[19][N], fr[N], flag[N]; ll ans = -1;
struct P {
int to; ll w; P(int To = 0, ll W = 0) : to(To), w(W) {}
inline bool operator<(const P &yy)const { return w > yy.w; }
}; vector<P> e[N];
ll depw[N];
ll a[N], b[N]; int la, lb;
vector<ll> hv[N];
multiset<ll> st;
template<typename T> inline void gi(T &x) {
x = 0; register char c = getchar(), pre = 0;
for(; c < '0' || c > '9'; pre = c, c = getchar());
for(; c >= '0' && c <= '9'; c = getchar()) x = 10ll * x + (c ^ 48);
if(pre == '-') x = -x;
}
void dfs(int u, int ff, int anc) {
if(ff == 1) anc = u; fr[u] = anc, fa[0][u] = ff;
rep(i, 1, 18) fa[i][u] = fa[i - 1][fa[i - 1][u]];
for(auto v : e[u]) if(v.to != ff) depw[v.to] = depw[u] + v.w, dfs(v.to, u, anc);
}
void solve(int u, int ff) {
if(flag[u] || e[u].size() == 1) return ;
int cnt = 0, now = 0;
for(auto v : e[u]) if(v.to != ff) ++cnt, solve(v.to, u), now += flag[v.to];
if(cnt == now) flag[u] = 1;
}
bool check(ll x) {
la = lb = 0; rep(i, 1, n) flag[i] = 0, hv[i].clear(); st.clear();
if(cnt[1]) { rep(i, 1, cnt[1]) a[++la] = x; }
rep(i, 2, n) if(cnt[i]) {
if(depw[i] <= x)
rep(j, 1, cnt[i]) {
if(depw[fr[i]] <= x - depw[i]) a[++la] = x - depw[i];
else hv[fr[i]].pb(x - depw[i]);
}
else {
int anc = i; ll tmp = x;
per(j, 18, 0)
if(fa[j][anc] && depw[anc] - depw[fa[j][anc]] <= tmp)
tmp -= depw[anc] - depw[fa[j][anc]], anc = fa[j][anc];
flag[anc] = 1;
}
}
for(auto v : e[1]) {
solve(v.to, 1), sort(hv[v.to].begin(), hv[v.to].end(), greater<ll>());
if(!flag[v.to]) {
multiset<ll>::iterator it = st.lower_bound(v.w);
if(it != st.end() && (!hv[v.to].size() || *it <= hv[v.to].back()))
st.erase(it), flag[v.to] = 1;
else if(hv[v.to].size()) hv[v.to].pop_back(), flag[v.to] = 1;
}
for(auto i : hv[v.to]) st.insert(i); if(!flag[v.to]) b[++lb] = v.w;
}
sort(a + 1, a + la + 1), sort(b + 1, b + lb + 1);
int p1 = 1, p2 = 1;
for(; p1 <= la && p2 <= lb; ++p1, ++p2) {
for(; p1 <= la && a[p1] < b[p2]; ++p1);
if(p1 > la) break;
}
return p2 > lb;
}
int main() {
gi(n);
rep(i, 2, n) { int x, y, z; gi(x), gi(y), gi(z), e[x].pb(P(y, z)), e[y].pb(P(x, z)); }
sort(e[1].begin(), e[1].end());
gi(m); rep(i, 1, m) { int x; gi(x), ++cnt[x]; }
dfs(1, 0, 0);
ll l = 0, r = 1e16, mid;
for(; l <= r;) mid = (l + r) / 2, check(mid) ? (ans = mid, r = mid - 1) : l = mid + 1;
printf("%lld
", ans);
return 0;
}