树上倍增¶
更多请参考 最近公共祖先
例题 #1 [NOIP2012 提高组] 疫情控制¶
题目描述
H 国有 $n $ 个城市，这 \(n\) 个城市用 \(n-1\) 条双向道路相互连通构成一棵树，$1 $ 号城市是首都，也是树中的根节点。
H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，首都是不能建立检查点的。
现在，在 H 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度（单位：小时）。
请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。
输入格式
第一行一个整数 $ n$，表示城市个数。
接下来的 \(n-1\) 行，每行 \(3\) 个整数，\(u,v,w\)，每两个整数之间用一个空格隔开，表示从城市 $u $ 到城市 $ v$ 有一条长为 \(w\) 的道路。数据保证输入的是一棵树，且根节点编号为 \(1\)。
接下来一行一个整数 \(m\)，表示军队个数。
接下来一行 $m $ 个整数，每两个整数之间用一个空格隔开，分别表示这 \(m\) 个军队所驻扎的城市的编号。
输出格式
一个整数，表示控制疫情所需要的最少时间。如果无法控制疫情则输出 \(-1\)。
- 对于 \(100\%\) 的数据，\(2\le m\le n≤5\times 10^4\)，\(0<w <10^9\)。
NOIP 2012 提高组 第二天 第三题
首先我们发现性质：
军队只能往上走，或者到达根节点后往下走一步。如果我们要贪心地求出最优分配，有一点困难，但是因为答案有单调性，所以我们可以二分答案。
那么我么发了也该时间t，我们就让所有军队尽可能往上跳，但是不能跳到根节点。
下面约定子树为以u为根节点的子树，其中u是首都的子节点。
此时我们会发现有些子树没有被封锁。那么有一些子树有军队来，那么我们就可以从中抽调1个军队来封锁。注意，封锁子树的军队**不一定**是来自它的军队。
那么我们自然是选择属于时间最短的军队来被抽调出来。然后我们就剩余了一些军队，这些军队各自有自己的剩余时间t。
我们把t排序，没有封锁的子树也排序，然后贪心分配。
具体来说，我们先将有剩余时间的军队拿出来，剩下的我们对每一个子树进行dfs，看看那些子树已经被封锁。
现在的问题就是我们有一些子树，还有一些停留在离首都1条边距离的军队。
这里有一个性质，即如果一个军队的剩余时间不足以让他到根节点后返回当前节点，那么他留在当前节点是最优的。因为我们考虑什么情况下我们需要把一个子树上的军队派遣到另外子树上去。反着来看，如果我们将子树u中的军队排到v去，那么将需要一个子树x的军队派到u。如果u的军队不满足可以折返的性质，那么就说明\(dis_v<dis_u\)，那么我们就可以人x的军队派到v而不是u去。
\(dis_u\)指的是u到速度的距离。
现在我们就是一些军队和一些未封锁的节点了。我们让这些军队全都到首都，然后排序，贪心分配即可。
/*
Keyblinds Guide
###################
@Ntsc 2024
- Ctrl+Alt+G then P : Enter luogu problem details
- Ctrl+Alt+B : Run all cases in CPH
- ctrl+D : choose this and dump to the next
- ctrl+Shift+L : choose all like this
- ctrl+K then ctrl+W: close all
- Alt+la/ra : move mouse to pre/nxt pos'
*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;
#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
// #define innt int
#define itn int
// #define inr intw
// #define mian main
// #define iont int
#define rd read()
int read(){
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
if constexpr (enable_dbg){
cerr << s;
if(1)cerr<<' ';
if constexpr (sizeof...(Args))
dbg(args...);
}
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
const int N = 1e6 + 5;
const int INF = 1e9;
const int M = 200;
const int MOD = 1e9 + 7;
const double eps=1e-4;
struct node{
int v,w;
};
vector<node>e[N];
void add(int a,int b,int c){
e[a].pb({b,c});
e[b].pb({a,c});
}
/*
发现性质：
军队只能往上走，或者到达根节点后往下走一步
*/
void dfs(int x,int f){
for(auto v:e[x]){
if(v.v==f)continue;
fa[v.v][0]=x;
d[v.v][0]=v.w;
forf(int i=1;i<=20;i++){
fa[v.v][i]=fa[fa[v.v][i-1]][i-1];
d[v.v][i]=d[v.v][i-1]+d[fa[v.v][i-1]][i-1];
}
dfs(v,x);
}
}
bool check(int t){
}
void solve(){
int n=rd;
for(int i=1;i<n;i++){
itn a=rd,b=rd,c=rd;
add(a,b,c);
}
int m=rd;
for(int i=1;i<=m;i++){
loc[i]=rd;
cnt[loc[i]]++;
}
if(m<e[1].size()){
puts("-1");
return ;
}
dfs(1,0);
itn l=0,r=INF;
int res=0;
while(l<=r){
int mid=l+r>>1;
if(check(mid))res=mid,r=mid-1;
else l=mid+1;
}
cout<<res<<endl;
}
signed main() {
// freopen("P2619_3.in","r",stdin);
// freopen("center.out","w",stdout);
int T=1;
while(T--){
solve();
}
return 0;
}