题目描述
H 国有 n 个城市，这 n 个城市用 n-1 条双向道路相互连通构成一棵树，1 号城市是首都，
也是树中的根节点。
H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境
城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境
城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，
首都是不能建立检查点的。
现在，在 H 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在
一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等
于道路的长度（单位：小时）。
请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。
输入输出格式
输入格式：
第一行一个整数 n，表示城市个数。
接下来的 n-1 行，每行 3 个整数，u、v、w，每两个整数之间用一个空格隔开，表示从
城市 u 到城市 v 有一条长为 w 的道路。数据保证输入的是一棵树，且根节点编号为 1。
接下来一行一个整数 m，表示军队个数。
接下来一行 m 个整数，每两个整数之间用一个空格隔开，分别表示这 m 个军队所驻扎
的城市的编号。
输出格式：
共一行，包含一个整数，表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1。
输入输出样例
4 1 2 1 1 3 2 3 4 3 2 2 2
3
说明
【输入输出样例说明】
第一支军队在 2 号点设立检查点，第二支军队从 2 号点移动到 3 号点设立检查点，所需
时间为 3 个小时。
【数据范围】
保证军队不会驻扎在首都。
对于 20%的数据，2≤ n≤ 10；
对于 40%的数据，2 ≤n≤50，0<w <10^5；
对于 60%的数据，2 ≤ n≤1000，0<w <10^6；
对于 80%的数据，2 ≤ n≤10,000；
对于 100%的数据，2≤m≤n≤50,000，0<w <10^9。
NOIP 2012 提高组 第二天 第三题
题解：
错误贪心乱搞 却AC的方法:
这题很巧，首先一秒意识到一支军队越往上走能控制的范围越大.
二分一个时间 t
定义：key[i]表示i能否控制整颗子树，bel[i]表示i属于哪一棵子树
我们要知道另一个子树到这颗子树来的军队，只需要到1的子节点处即可
于是我们把所有军队先尽量往上跳，直到跳到1，至于没有跳到1的，如果它跳到的位置key==1 那么我们就把这颗子树标记
然后把所有军队的剩余时间存到数组里并从大到小排序，然后就是把每一个需要被控制的子树丢进一个数组，也从大到小排序，最后一一比较.
还有一种情况：一颗子树内原有的军队跑到别的子树，而顾不上自己的子树,于是我们开一个数组minst[i]表示经过该节点的剩余时间最小的军队, 然后如果这个军队没用过，我们就用minst[i].
正确性证明：如果minst[i]没用过那么j军队的剩余时间>=minst[i] 所以用j来控制其他子树更有用
另 跳用倍增即可，二分的r不要开太大.
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 typedef long long ll; 8 const int N=50005,INF=1999999999; 9 int gi(){ 10 int str=0;char ch=getchar(); 11 while(ch>'9' || ch<'0')ch=getchar(); 12 while(ch>='0' && ch<='9')str=str*10+ch-'0',ch=getchar(); 13 return str; 14 } 15 int n,num=0,head[N],cc=0,m,s[N],fa[N][21],dis[N][21],du[N],maxdep,top=0,tt=0,dt[N],bel[N],minst[N],ddt=0; 16 struct QUEUE{ 17 int t,id; 18 }q[N],ct[N]; 19 bool key[N],d[N],ud[N]; 20 struct Lin{ 21 int next,to,dis; 22 }a[N*2]; 23 void init(int x,int y,int z){ 24 a[++num].next=head[x];a[num].to=y;a[num].dis=z;head[x]=num; 25 a[++num].next=head[y];a[num].to=x;a[num].dis=z;head[y]=num; 26 } 27 void prework(int x,int last) 28 { 29 int u; 30 if(key[last])key[x]=true; 31 else key[x]=false; 32 if(du[last]>2 && last!=1)key[x]=false; 33 for(int i=head[x];i;i=a[i].next) 34 { 35 u=a[i].to; 36 if(u==last)continue; 37 dis[u][0]=a[i].dis;fa[u][0]=x;dt[u]=dt[x]+a[i].dis; 38 prework(u,x); 39 } 40 } 41 void belong(int x,int last,int bl){ 42 bel[x]=bl; 43 for(int i=head[x];i;i=a[i].next) 44 if(a[i].to!=last)belong(a[i].to,x,bl); 45 } 46 void gf(){ 47 for(int j=1;j<=maxdep;j++) 48 for(int i=1;i<=n;i++) 49 fa[i][j]=fa[fa[i][j-1]][j-1],dis[i][j]=dis[i][j-1]+dis[fa[i][j-1]][j-1]; 50 for(int i=head[1];i;i=a[i].next)belong(a[i].to,1,a[i].to); 51 } 52 int jump(int x,int lim) 53 { 54 for(int j=maxdep;j>=0;j--) 55 { 56 if(fa[x][j]!=0 && dis[x][j]<=lim) 57 { 58 lim-=dis[x][j]; 59 x=fa[x][j]; 60 } 61 if(lim==0)break; 62 } 63 return x; 64 } 65 bool comp(const QUEUE &p,const QUEUE &q){return p.t>q.t;} 66 bool pd() 67 { 68 memset(ud,0,sizeof(ud)); 69 int u; 70 if(tt<top)return false; 71 for(int i=1,j=1;i<=top;i++) 72 { 73 u=ct[i].id; 74 if(minst[u]!=INF && !ud[minst[u]]){ud[minst[u]]=true;continue;} 75 while(ud[q[j].id] && j<=tt)j++; 76 if(j>tt)return false; 77 if(q[j].t<ct[i].t)return false; 78 ud[q[j].id]=true; 79 } 80 return true; 81 } 82 bool check(int ff) 83 { 84 for(int i=1;i<=n;i++)minst[i]=INF,d[i]=false; 85 top=0;tt=0;int cnt=0; 86 for(int i=1;i<=m;i++) 87 { 88 int to=jump(s[i],ff); 89 if(du[to]==1)cnt++; 90 if(to==1){ 91 tt++; 92 q[tt].id=tt;q[tt].t=ff-dt[s[i]]; 93 if(minst[bel[s[i]]]==INF)minst[bel[s[i]]]=tt; 94 if(q[tt].t<q[minst[bel[s[i]]]].t)minst[bel[s[i]]]=tt; 95 } 96 else if(key[to])d[bel[to]]=true; 97 } 98 if(ddt==cnt)return true; 99 sort(q+1,q+tt+1,comp); 100 int u; 101 for(int i=head[1];i;i=a[i].next)if(!d[a[i].to])ct[++top].id=a[i].to,ct[top].t=a[i].dis; 102 if(!top)return true; 103 sort(ct+1,ct+top+1,comp); 104 return pd(); 105 } 106 int main() 107 { 108 int x,y,z; 109 n=gi();maxdep=log(n)/log(2); 110 for(int i=1;i<n;i++) 111 { 112 x=gi();y=gi();z=gi(); 113 init(x,y,z);du[x]++;du[y]++; 114 if(x==1 || y==1)cc++; 115 } 116 for(int i=1;i<=n;i++)if(du[i]==1)ddt++; 117 m=gi(); 118 for(int i=1;i<=m;i++)s[i]=gi(); 119 if(m<cc){printf("-1");return 0;} 120 key[0]=true; 121 prework(1,0);gf(); 122 int l=0,r=19999999,mid,ans=-2; 123 if(check(0)){ 124 printf("0"); 125 return 0; 126 } 127 while(l<=r) 128 { 129 mid=(l+r)>>1; 130 if(check(mid))ans=mid,r=mid-1; 131 else l=mid+1; 132 } 133 printf("%d",ans); 134 return 0; 135 }