思路分析
- 军队所在的城市距离首都越近,亦或在树上深度越低,所“控制”的范围越大。所以根据贪心思想,在时间足够的情况下,军队要尽量往上爬(不能驻扎首都)。
- 在到达根节点前,绝对不要向下走。因为留在高处省时间,控制范围也大。除非首都的其他子节点没有足够的军队,需要去“救火”
- 军队可以同时移动,即我们所求的是军队移动时间最大值的最小值
$\to$ 二分答案
具体操作
- 二分时间。接下来只需验证在此时间限制内能否封锁疫情
- 使用倍增的方法,在时间限制内把所有军队尽量向上提,最高不超过根节点
- 如果当前军队到达不了根节点:直接驻扎在所能到达最高的地方
如果当前军队可以到达根节点:那么记录一下它的编号和它到达根节点后还可以走的时间 rest
。如果这个军队 $i$ 在根节点的子树 $x$ 中,那么记录一下子树 $x$ 的符合这个条件的点中,走到根节点后剩余路程最短的点。
- dfs 寻找还未被封锁的子树。若根节点或根节点的所有儿子都有军队,则认为这棵树已被封锁
- 将之前记录的可以走到首都的军队按剩余时间(最多还能走多久)排序,还未被封锁的子树按离首都距离排序。如果在限定时间内有可行解,那么让剩余时间越多的军队去驻扎越远的城市必然可行。
- 如果某颗尚未被封锁的子树内有可以到达首都的军队,就让其中剩余时间最少的来驻扎本身这颗子树。(剩余时间长的用于支援其他子树)
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 50005;
struct Edge {
ll v, w, next;
} pool[MAXN<<1];
ll n,m,nn,head[MAXN];
ll anc[MAXN][20];//ancestor[i][j]表示i点的2^j层父亲
ll dis[MAXN][20];//dis[i][j]表示i点到2^j层父亲的距离
ll dep[MAXN];//每个点的深度
ll maxDis;//从树根到叶子结点最大距离
void addEdge(ll u, ll v, ll w) {
pool[++nn].v = v;
pool[nn].w = w;
pool[nn].next = head[u];
head[u] = nn;
}
//遍历树,找到每个点的祖先和与祖先的距离
void dfs(ll u, ll father, ll weight) {
dep[u] = dep[father] + 1;
anc[u][0] = father;
dis[u][0] = weight;
for (int i = 1; (1 << i) <= dep[u]; ++i) {
anc[u][i] = anc[anc[u][i - 1]][i - 1];
dis[u][i] = dis[u][i - 1] + dis[anc[u][i - 1]][i - 1];
maxDis = max(maxDis, dis[u][i]);
}
for (int i = head[u]; i; i = pool[i].next) {
int v = pool[i].v;
if (v != father) {
int w = pool[i].w;
dfs(v, u, w);
}
}
}
ll troop[MAXN];//军队初始所在城市编号
ll control[MAXN];//某城市是否有军队控制
struct Rest {
ll dis, id;
bool operator<(const Rest &other) const {
return dis > other.dis;
}
};
Rest restTroop[MAXN];//停留在首都的军队
Rest restChild[MAXN];//首都尚未被封锁的孩子
ll remainDis[MAXN];//途径本点到达首都的军队,剩余路程最少的军队的路程
ll goThrough[MAXN];//途径本点到达首都的军队,剩余路程最少的军队的编号
ll used[MAXN];//某只在首都的军队是否被用过
ll nt;//到达首都的军队个数
ll nc;//尚未被封锁的孩子个数
//检查目前疫情能否被控制
bool checkControl(ll u, ll father, ll weight) {
if (control[u]) {
return true;
}
bool hasChild = false;
bool canControl = true;
for (int i = head[u]; i; i = pool[i].next) {
ll v = pool[i].v;
if (v == father) continue;
hasChild = true;
if (!checkControl(v, u, pool[i].w)) {
canControl = false;
}
}
if (!hasChild) canControl = false;
//把所有首都的没被控制的孩子放进restChild中
if (!canControl && dep[u] == 2) {
restChild[nc].dis = weight;
restChild[nc++].id = u;
}
return canControl;
}
bool check(ll mid) {
nt = 0;
nc = 0;
for (int i = 0; i <= n; ++i) {
control[i] = 0;
goThrough[i] = 0;
remainDis[i] = 0;
used[i] = 0;
}
for (int i = 1; i <= m; ++i) {
ll u = troop[i];
ll d = 0;
//从当前点尽量往上提,但是不要提到根节点
for (int j = 17; j >= 0; --j) {
if (anc[u][j] > 1 && d + dis[u][j] <= mid) {
d += dis[u][j];
u = anc[u][j];
}
}
//如果当前军队能到首都,记下来从首都的哪个儿子上去的
if (anc[u][0] == 1 && d + dis[u][0] <= mid) {
restTroop[nt].id = i;
restTroop[nt].dis = mid - d - dis[u][0];
if (goThrough[u] == 0 || remainDis[u] > restTroop[nt].dis) {
goThrough[u] = i;
remainDis[u] = restTroop[nt].dis;
}
nt++;
} else {
//到不了首都,就留下控制当前城市
control[u] = 1;
}
}
if (checkControl(1, 0, 0)) {
return true;
}
sort(restChild, restChild + nc);
sort(restTroop, restTroop + nt);
ll j = 0;
for (int i = 0; i < nc; ++i) {
ll child = restChild[i].id;
if (goThrough[child] != 0 && used[goThrough[child]] == 0) {
used[goThrough[child]] = 1;
continue;
}
while (j < nt && used[restTroop[j].id]) {
j++;
}
if (j == nt) return false;
if (restTroop[j].dis < restChild[i].dis) return false;
used[restTroop[j].id] = 1;
}
return true;
}
int main() {
scanf("%lld", &n);
for (int i = 0; i < n - 1; ++i) {
ll u, v, w;
scanf("%lld%lld%lld", &u, &v, &w);
addEdge(u, v, w);
addEdge(v, u, w);
}
scanf("%lld", &m);
for (int i = 1; i <= m; ++i) {
scanf("%lld", &troop[i]);
}
dfs(1, 0, 0);
ll low = 0;
ll high = maxDis * 2;
ll ans = -1;
while (low <= high) {
ll mid = (low + high) >> 1;
if (check(mid)) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
printf("%lld\n", ans);
return 0;
}