传送门
problem
H 国有
n
n
n 个城市，这
n
n
n 个城市用
n
−
1
n-1
n−1 条双向道路相互连通构成一棵树，
1
1
1 号城市是首都，也是树中的根节点。
H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，首都是不能建立检查点的。
现在，在 H 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度。
请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。
数据范围：
2
≤
m
≤
n
≤
3
×
1
0
5
2≤m≤n≤3\times 10^5
2≤m≤n≤3×105，
0
<
w
<
1
0
9
0<w <10^9
0<w<109。
solution
这道题也很不错，感觉 NOIP 2012 的题都挺好的。
首先，题目要求我们最小化最大的时间，不难想到二分，考虑怎么
c
h
e
c
k
check
check 二分的答案
λ
\lambda
λ。
由于深度越浅的点能控制的叶子节点越多，所以一个显然的贪心就是，尽量把军队往上提。如果一个军队提到的最上面的点
x
≠
1
x\ne 1
x=1，那么直接把
x
x
x 控制了即可。否则我们记一下能提到
1
1
1 的那些军队（先不控制任何点）以及他们还剩的距离，他们就有可能去其他子树进行控制了。
接下来就
d
f
s
dfs
dfs 一遍求
1
1
1 的哪些子树不能通过当前已控制的点来控制其所有叶节点，需要借助那些能提到
1
1
1 的军队。
由于剩余时间更多的军队肯定会拿去和距离更长的点匹配，我们排个序贪心匹配即可。注意如果一些点内本来就有军队（现在提到了
1
1
1 号点），那么这其中剩余路径最小的匹配该点可能会更优，要特判一下。
时间复杂度
O
(
n
log
n
)
O(n\log n)
O(nlogn)。
code
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std
;
typedef long long ll
;
namespace IO
{
const int Rlen
=1<<22|1;
char buf
[Rlen
],*p1
,*p2
;
inline char gc(){
return (p1
==p2
)&&(p2
=(p1
=buf
)+fread(buf
,1,Rlen
,stdin),p1
==p2
)?EOF:*p1
++;
}
template<typename T
>
inline T
Read(){
char c
=gc();T x
=0,f
=1;
while(!isdigit(c
)) f
^=(c
=='-'),c
=gc();
while( isdigit(c
)) x
=(x
+(x
<<2)<<1)+(c
^48),c
=gc();
return f
?x
:-x
;
}
inline int in() {return Read
<int>();}
}
using IO
::in
;
const int N
=3e5+5;
int n
,m
,t
;
int city
[N
],fa
[N
][21],first
[N
],v
[N
<<1],w
[N
<<1],nxt
[N
<<1];
ll d
[N
][21];
void add(int x
,int y
,int z
){
nxt
[++t
]=first
[x
],first
[x
]=t
,v
[t
]=y
,w
[t
]=z
;
}
void dfs1(int x
){
for(int i
=1;i
<=20;++i
){
fa
[x
][i
]=fa
[fa
[x
][i
-1]][i
-1];
d
[x
][i
]=d
[x
][i
-1]+d
[fa
[x
][i
-1]][i
-1];
}
for(int i
=first
[x
];i
;i
=nxt
[i
]){
int to
=v
[i
];
if(to
==fa
[x
][0]) continue;
fa
[to
][0]=x
,d
[to
][0]=w
[i
];
dfs1(to
);
}
}
int a
,b
,occ
[N
],used
[N
];
typedef pair
<ll
,int> pli
;
pli A
[N
],B
[N
],rest
[N
];
void Clear(){
a
=0,b
=0;
memset(occ
,0,sizeof(occ
));
memset(rest
,0,sizeof(rest
));
memset(used
,0,sizeof(used
));
}
bool dfs2(int x
){
bool leave
=1,flag
=1;
if(occ
[x
]) return true;
for(int i
=first
[x
];i
;i
=nxt
[i
]){
int to
=v
[i
];
if(to
==fa
[x
][0]) continue;
leave
=0;
if(!dfs2(to
)){
flag
=0;
if(x
==1) B
[++b
]=pli(w
[i
],to
);
else return false;
}
}
if(leave
) return false;
return flag
;
}
bool comp(const pli
&p
,const pli
&q
) {return p
.fi
>q
.fi
;}
bool check(ll mid
){
Clear();
for(int i
=1;i
<=m
;++i
){
ll x
=city
[i
],cost
=0;
for(int j
=20;~j
;--j
)
if(fa
[x
][j
]>1&&cost
+d
[x
][j
]<=mid
)
cost
+=d
[x
][j
],x
=fa
[x
][j
];
if(fa
[x
][0]==1&&cost
+d
[x
][0]<=mid
){
A
[++a
]=pli(mid
-cost
-d
[x
][0],i
);
if(!rest
[x
].fi
||rest
[x
].fi
>A
[a
].fi
) rest
[x
]=A
[a
];
}
else occ
[x
]=1;
}
if(dfs2(1)) return true;
sort(A
+1,A
+a
+1,comp
),sort(B
+1,B
+b
+1,comp
);
int now
=0;used
[0]=1;
for(int i
=1;i
<=b
;++i
){
if(!used
[rest
[B
[i
].se
].se
]){
used
[rest
[B
[i
].se
].se
]=1;
continue;
}
while(now
<=a
&&(used
[A
[now
].se
]||A
[now
].fi
<B
[i
].fi
)) ++now
;
if(now
>a
) return false;
used
[A
[now
].se
]=1;
}
return true;
}
int main(){
n
=in();
for(int i
=1,x
,y
,z
;i
<n
;++i
){
x
=in(),y
=in(),z
=in();
add(x
,y
,z
),add(y
,x
,z
);
}
dfs1(1),m
=in();
for(int i
=1;i
<=m
;++i
) city
[i
]=in();
ll l
=0,r
=3e14,ans
=-1,mid
;
while(l
<=r
) check(mid
=(l
+r
)>>1)?(ans
=mid
,r
=mid
-1):l
=mid
+1;
printf("%lld\n",ans
);
return 0;
}
