题目描述 Description
H 国有 n 个城市，这 n 个城市用 n-1 条双向道路相互连通构成一棵树，1 号城市是首都，
也是树中的根节点。
H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境
城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境
城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，
首都是不能建立检查点的。
现在，在 H国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军
队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在
一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等
于道路的长度（单位：小时）。
请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。
输入描述 Input Description
第一行一个整数 n，表示城市个数。
接下来的 n-1 行，每行 3 个整数，u、v、w，每两个整数之间用一个空格隔开，表示从
城市 u 到城市 v 有一条长为 w 的道路。数据保证输入的是一棵树，且根节点编号为 1。
接下来一行一个整数 m，表示军队个数。
接下来一行 m 个整数，每两个整数之间用一个空格隔开，分别表示这 m 个军队所驻扎
的城市的编号。
输出描述 Output Description
共一行，包含一个整数，表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1。
样例输入 Sample Input
4
1 2 1
1 3 2
3 4 3
2
2 2
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
【输入输出样例说明】
第一支军队在 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。
分类标签 Tags 点此展开
题解：（tyts）
这道题主要算法就是贪心以及倍增和二分答案。首先我们对树进行处理，记录每个点2的次幂的father是谁，以及每个点到达根节点的距离是多少。我们发现对于当前的点，在给定的时间内只能往上走，因为往下走能看守的点会减少并且浪费时间。往下走的充要条件是到达了根节点，然后从根节点退下一格，到达另一个叶子。我们预处理每个节点如果看守住了，相当于看守住了最靠近根节点的哪个节点。我们发现如果一个点只有一个儿子，那么看守它的儿子也就相当于看守了它。 接下来我们考虑对于给定的时间k，如何检验它是否合法。我们把每一个有军队的节点向靠近根节点的方向走，直到不能走为止。如果一个军队没有走到根节点，那么他显然只能去看守最后到达的那个节点，这已经是最优方案。接下来我们考虑对于到达根节点的所有点中，我们记录每个点的两个属性：一是他来自哪里，二是他还能走多长时间的路。接下来的贪心策略是如果一个点的剩余路程不足以使得他回到他来自的哪个节点，我们则把他退回去，并且删掉这样的点。接下来我们把剩余到达根节点的点按照剩余路程从小到大排序，记为数组A，把根节点的叶子节点中没有被覆盖的节点取出，并且按照到达根节点的距离进行从小到大排序，记为数组B。最后我们把两个数组进行归并，用A中小的去覆盖B中小的，如果B可以被完全覆盖则当前的k合法，否则不合法。时间复杂度为O(nlognlogAns)。
ps：顺便复习一下倍增lca
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<ctime> #include<iostream> #include<algorithm> #include<string> #include<vector> #include<queue> #include<stack> #include<map> using namespace std; #define N 100010 #define ll long long #define xx first #define yy second typedef pair<int,int> diy; inline const int read(){ register int x=0,f=1; register char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline const char in(){ for(register char ch=getchar();;ch=getchar()) if((ch>='A'&&ch<='Z')) return ch; } struct ss{ int v,w,next; }e[N<<1]; struct node{ int u,v; }b[N],c[N]; int tot,head[N]; int dep[N],f[N][21],g[N][21],a[N]; bool vis[N]; int n,m,l,r,mid; void add(int x,int y,int z){ e[++tot].v=y; e[tot].w=z; e[tot].next=head[x]; head[x]=tot; } bool cmp(const node &a,const node &b){ return a.v<b.v;//因为我们要控制所有叶子节点，也就是所有的1的儿子，所以我们把剩余的军队和剩余的1的儿子拉出来，排个序，贪心地匹配。 } void dfs(int x,int y){ for(int i=head[x];i;i=e[i].next){ if(e[i].v!=y){ f[e[i].v][0]=x;//f[i][0]保存i的父节点为x g[e[i].v][0]=e[i].w;//同步记录该边的权值 dep[e[i].v]=dep[x]+1;//当前点深度+1 dfs(e[i].v,x); } } } int lca(int a,int b){//从深度大的节点上升至深度小的节点同层，如果此时两节点相同直接返回此节点，即lca。 //否则，利用倍增法找到最小深度的: g[x][j]!=g[y][j]，此时他们的父亲g[x][0]即lca。 if(dep[a]<dep[b]) swap(a,b); int t=dep[a]-dep[b]; for(int i=0;i<=20;i++){ if((1<<i)&t){ a=f[a][i]; } } if(a==b) return a; for(int i=20;i>=0;i--){//倍增法，每次向上进深度2^j，找到最近公共祖先的子结点 if(f[a][i]!=f[b][i]){ a=f[a][i]; b=f[b][i]; } } return f[a][0]; } void color(int x){//如果不能到达1点，那就停在最高点 bool p=1,q=0; for(int i=head[x];i;i=e[i].next){ if(e[i].v!=f[x][0]){ color(e[i].v); p&=vis[e[i].v]; q=1; } } if(p&&q&&x!=1) vis[x]=1; } bool check(int x){ memset(vis,0,sizeof vis); int cnt=0,top=0; for(int i=1;i<=m;i++){//枚举每一个军队可以上跳到哪个祖先 int y=a[i],z=0,k=a[i]; for(int j=20;j>=0;j--){ if(f[y][j]&&z+g[y][j]<=x){ z+=g[y][j]; y=f[y][j]; } } if(y!=1) vis[y]=1; else{//如果一个军队能够到达1，也就能够直接到达它所属的那个1的儿子，所以每个军队就有两个决策，也是贪心 b[++cnt].v=x-z;//军队移动的距离 y=a[i]; for(int j=20;j>=0;j--){//再往下找 if(f[y][j]>1){ y=f[y][j]; } } b[cnt].u=y; } } color(1);//我们对于不能跳到1点的军队就让他停在最高点。 for(int i=head[1];i;i=e[i].next){ if(!vis[e[i].v]){ c[++top].u=e[i].v; c[top].v=e[i].w; } } sort(b+1,b+cnt+1,cmp);//升序：剩余路程 sort(c+1,c+top+1,cmp);//升序：到根节点的距离（没有覆盖的跟的叶子节点） int j=1; c[top+1].v=0x3f3f3f3f;//限制 for(int i=1;i<=cnt;i++){ if(!vis[b[i].u]) vis[b[i].u]=1; else if(b[i].v>=c[j].v) vis[c[j].u]=1; while(vis[c[j].u]) j++; } return j>top;//能否往上跳 } int main(){ n=read(); for(int i=1,x,y,z;i<n;i++) x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z),r+=z; m=read(); for(int i=1;i<=m;i++) a[i]=read(); dfs(1,1); for(int j=1;j<=20;j++){//初始各个点的2^j祖先是谁 ,其中 2^j (j =0...log(该点深度))倍祖先，1倍祖先就是父亲，2倍祖先是父亲的父亲......。 for(int i=1;i<=n;i++){//f[i][j]表示i结点的第2^j祖先 f[i][j]=f[f[i][j-1]][j-1];//i的第2^j祖先就是i的第2^(j-1)祖先的第2^(j-1)祖先 g[i][j]=g[f[i][j-1]][j-1]+g[i][j-1]; } } while(l<r){//答案在 0-所有边权值的和 之中 mid=(l+r>>1); if(check(mid)) r=mid; else l=mid+1; } printf("%d ",check(l)?l:-1); return 0; }