题意：
给出一颗n个节点有边权的树 和m个军队所在的位置 军队从某节点移动到相邻节点要花费边长度的时间 求最少要多少时间使得根节点（编号为1）到每个叶子的路径上最少有一支军队（根节点不能有军队）
题解：
我们可以二分答案 那么问题就转换为 在t的时间内军队能否控所有点
显然一支军队在到根节点之前 如果能继续向上走 那么这支军队能控制的点就会更多
维护bo[i]表示 从该点到所有该点子树的叶子节点路径上是否都有军队
对于每个不能走到根节点的军队 就让他尽量向上走 直到不能走为止 将该点的bo值赋为1 然后可以用拓扑算出bo数组
这样 根节点的所有儿子中bo为1的点就不用管 而剩下的点就需要派能走到根节点的军队到这些点控制
于是问题转换为 有n0个点需要被控制 且控制该点需要Li的时间 还有m0支军队 每支军队有ti的时间 求这m0支军队是否能控制这n0个点
这原本这样将L和t分别排序 贪心用两个指针一个个扫就行了
但是要注意的是如果军队j就是从i点走到首都的 那么该军队不论有多少剩余时间都能控制该点（去年noip考试的时候好像就是没想到这点）
这个问题我们只要做一个小转换就行了 如果i点有军队从该点到达首都 那么用minarm[i]记下这些军队中剩余时间最少的是谁 当指针扫到i时先判断minarm[i]是否被用过了 如果没有 那么用minarm[i]来控制i 否则再在j指针上找军队
证明：如果minarm[i]没被使用 那么t[j]>=t[minarm[i]] 所以在i点如果用minarm[i]则能省下一个剩余时间更多的军队 对于之后可能用到minarm[i]的点完全可以用j点代替
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::sort;
const int N=;
struct inli{
int next,data,lon;
inli(const int a=,const int b=,const int c=):
next(a),data(b),lon(c){}
}line[N*];
struct info{
int t,s;
info(const int a=,const int b=):
t(a),s(b){}
}ar[N],ci[N];
inline bool cmp(info a,info b){ return a.s>b.s; }
int n,m,na,nc,fat[N],ti[N],gra[N],dis[N],arm[N],nl,son[N],mint[N],add,boo[N];
int max(int x,int y){ return x>y ? x : y; }
void dfs(int t){
int res=-,bo1=,bo2=;
for (int i=son[t];i;i=line[i].next)
if (line[i].data!=fat[t]){
int ne=line[i].data;
dfs(ne);
if (ti[ne]==-) bo2=;
if (ti[ne]-line[i].lon>=) bo1=;
res=max(res,ti[ne]-line[i].lon);
}
if (t!= && line[son[t]].next){
if (bo1) ti[t]=max(ti[t],res);
else if (bo2) ti[t]=max(ti[t],-);
else ti[t]=max(ti[t],);
}
}
void maketi(int t){
for (int i=;i<=m;i++)
if (dis[arm[i]]>=t) ti[arm[i]]=t;
dfs();
}
void makear(int t){
na=;
for (int i=;i<=m;i++)
if (dis[arm[i]]<t) ar[++na]=info(gra[arm[i]],t-dis[arm[i]]);
sort(ar+,ar+na+,cmp);
for (int i=;i<=na;i++){
int x=ar[i].t;
if (mint[x]==) mint[x]=i;
else if (ar[mint[x]].s>ar[i].s) mint[x]=i;
}
}
void makeci(){
nc=;
for (int i=son[];i;i=line[i].next)
if (ti[line[i].data]==-) ci[++nc]=info(line[i].data,line[i].lon);
sort(ci+,ci+nc+,cmp);
}
bool work(){
if (na<nc) return ;
memset(boo,,sizeof(boo));
for (int i=,j=;i<=nc;i++)
if (!boo[mint[ci[i].t]] && mint[ci[i].t]) boo[mint[ci[i].t]]=;
else{
while (boo[j] && j<=na) ++j;
if (j>na) return ;
if (ar[j].s<ci[i].s) return ;
boo[j++]=;
}
return ;
}
bool check(int t){
memset(ti,-,sizeof(ti));
memset(mint,,sizeof(mint));
maketi(t);
makear(t);
makeci();
return work();
}
int getans(){
int l=-,r=,mid;
while (l+<r){
mid=(l+r)/;
if (check(mid)) r=mid;
else l=mid;
}
return r;
}
void makefat(int t){
for (int i=son[t];i;i=line[i].next)
if (line[i].data!=fat[t]){
int ne=line[i].data;
if (t==) gra[ne]=ne;
else gra[ne]=gra[t];
fat[ne]=t;
dis[ne]=dis[t]+line[i].lon;
makefat(ne);
}
}
int main(){
freopen("blockade.in","r",stdin);
freopen("blockade.out","w",stdout);
scanf("%d",&n);
for (int x,y,z,i=;i<n;i++){
scanf("%d%d%d",&x,&y,&z);
line[++nl]=inli(son[x],y,z),son[x]=nl;
line[++nl]=inli(son[y],x,z),son[y]=nl;
if (x== || y==) ++add;
}
makefat();
scanf("%d",&m);
if (m<add){
printf("-1");
return ;
}
for (int i=;i<=m;i++) scanf("%d",&arm[i]);
sort(arm+,arm+m+);
printf("%d",getans());
fclose(stdin);
fclose(stdout);
}