题目描述
HHH 国有 nn n个城市，这 nnn 个城市用n−1 n-1 n−1条双向道路相互连通构成一棵树，11 1号城市是首都，也是树中的根节点。
HH H国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，首都是不能建立检查点的。
现在，在 HHH 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度（单位：小时）。
请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。
输入输出格式
输入格式：第一行一个整数n nn，表示城市个数。
接下来的 n−1n-1n−1 行，每行3 3 3个整数，u,v,wu,v,wu,v,w，每两个整数之间用一个空格隔开，表示从城市 uu u到城市v vv 有一条长为 www 的道路。数据保证输入的是一棵树，且根节点编号为 111。
接下来一行一个整数 mmm，表示军队个数。
接下来一行 mm m个整数，每两个整数之间用一个空格隔开，分别表示这 mmm 个军队所驻扎的城市的编号。
输出格式：一个整数，表示控制疫情所需要的最少时间。如果无法控制疫情则输出−1-1−1。
输入输出样例
说明
【输入输出样例说明】
第一支军队在 222 号点设立检查点，第二支军队从 222 号点移动到3 33 号点设立检查点，所需时间为 333 个小时。
【数据范围】
保证军队不会驻扎在首都。
对于 20%的数据，2≤n≤102≤ n≤ 102≤n≤10；
对于 40%的数据，2≤n≤50,0<w<1052 ≤n≤50,0<w <10^52≤n≤50,0<w<105；
对于 60%的数据，2≤n≤1000,0<w<1062 ≤ n≤1000,0<w <10^62≤n≤1000,0<w<106；
对于 80%的数据，2≤n≤10,0002 ≤ n≤10,0002≤n≤10,000；
对于 100%的数据，2≤m≤n≤50,000,0<w<1092≤m≤n≤50,000,0<w <10^92≤m≤n≤50,000,0<w<109。
NOIP 2012 提高组 第二天 第三题
很有意思的一题；
用到了倍增，二分，树上操作
因为答案具有单调性所以选择二分答案；
判断过程中将所有士兵往上跳（长度小于等于二分值）
判断该士兵能否到1节点，若能则将其压入数组，并存入剩余步数（用于贪心
不能则标记能到的最高点；
之后依次判断每个节点控制的子树底端是否已被覆盖，没有的话就将root点压入一个数组，并存入到1点的距离
之后就模拟看能否将每个点覆盖
（loj数据有点强过不了。。只过了洛谷的。。）
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 3e5+10;
ll n,head[maxn],size,r[maxn],f[maxn][20],maxd,deep[maxn],m,val[maxn],root[maxn],tt,ct;
ll dis[maxn][30];
struct edge{
ll v,w,nex;
}e[maxn<<1];
struct node{
ll id,w;
}kzqc[maxn],wbkz[maxn];
bool cmp(node a,node b){
return a.w<b.w;
}
void adde(ll u,ll v,ll w){
e[size].v=v;e[size].w=w;e[size].nex=head[u];head[u]=size++;
}
bool vis[maxn],vis2[maxn];
void dfs(){
queue<int>q;
q.push(1);
while(!q.empty()){
int u=q.front();q.pop();
if(f[u][0]!=-1) maxd=max(maxd,deep[u]=deep[f[u][0]]+1);
for(int i=head[u];~i;i=e[i].nex){
int v=e[i].v;
if(v==f[u][0]) continue;
if(u==1) root[v]=v;
else root[v]=root[u];
dis[v][0]=e[i].w;f[v][0]=u;
q.push(v);
}
}
}
void doubling(){
for(ll j=1;j<=maxd;j++)
for(ll i=1;i<=n;i++){
if(f[i][j-1]!=-1) f[i][j]=f[f[i][j-1]][j-1],dis[i][j]=dis[i][j-1]+dis[f[i][j-1]][j-1];
}
}
bool _dfs(ll u){
if(r[u]==1&&!vis[u]) return 1;
for(ll i=head[u];~i;i=e[i].nex){
if(e[i].v==f[u][0]) continue;
if(vis[u]) vis[e[i].v]=vis[u];
if(_dfs(e[i].v)) return 1;
}
return 0;
}
bool check(ll mid){
memset(kzqc,0,sizeof(kzqc));memset(wbkz,0,sizeof(wbkz));memset(vis,0,sizeof(vis));memset(vis2,0,sizeof(vis2));
tt=0,ct=0;
for(ll i=1;i<=m;i++){
ll lu=mid;ll u=val[i];
for(ll j=maxd;j>=0;j--){
if(f[u][j]!=-1&&dis[u][j]<=lu) lu-=dis[u][j],u=f[u][j];
}
if(u==1) {
kzqc[++tt].id=root[val[i]],kzqc[tt].w=lu;
}
else vis[u]=1;
}
for(ll i=head[1];~i;i=e[i].nex){
ll v=e[i].v;
if(!vis[v]&&_dfs(v)){
wbkz[++ct].id=root[v],wbkz[ct].w=e[i].w;vis2[root[v]]=1;
}
}
sort(kzqc+1,kzqc+1+tt,cmp);sort(wbkz+1,wbkz+1+ct,cmp);
ll t=1;
for(ll i=1;i<=tt;i++){
if(vis2[kzqc[i].id]) vis2[kzqc[i].id]=0;
else if(kzqc[i].w>=wbkz[t].w) vis2[wbkz[t].id]=0;
while(!vis2[wbkz[t].id]) {
t++;if(t>ct) return 1;
}
}
return t>ct;
}
int main(){
freopen("in.txt","r",stdin);
scanf("%lld",&n);
memset(f,-1,sizeof(f));memset(head,-1,sizeof(head));
ll lef=0,righ=12484069034;
for(ll i=1;i<n;i++){
ll u,v,w;scanf("%lld%lld%lld",&u,&v,&w);
adde(u,v,w);adde(v,u,w);r[u]++,r[v]++;;
}
dfs();
maxd=(ll)(log(maxd)/log(2));
doubling();
scanf("%lld",&m);
ll ans=-1;
for(int i=1;i<=m;i++) scanf("%lld",val+i);
while(lef<=righ){
ll mid=(lef+righ)>>1;
if(check(mid)) {ans=mid;righ=mid-1;}
else lef=mid+1;
}
printf("%lld",ans);
return 0;
}