P1084 NOIP2012T6 疫情控制 二分+贪心+LCA

题意：在一棵树上有多个节点，求让这些军队将所有的从根节点到叶子节点的路径被一个或以上的军队堵住

因为所有军队可以同时移动，所以本题可简化成为：求出所有军队的最长移动时间，并使这个时间最小

解法：二分+贪心+LCA

1.二分；由于题目所给数据非常的大，而且需要对每一种做法都进行检验明显是不行的，所以需要二分

2.贪心；任意一个军队只要每往上走一步，那么那支军队就能多控制一个节点，这样明显是优的； 做法：让每一支军队在二分的时间内尽量的往上走，此时，可以分为两种情况：

<1>到不了树根，那就让它呆在那

<2>到得了树根，记录下这支军队还剩下多少时间

而对于这第二种情况，如果这支军队剩下的时间不足以让它返回到它经过的树根的儿子，并且它经过的树根的儿子没有军队驻扎，那么就让它退回去； 如果这支军队剩下的时间足以让它返回，那么就留下

接下来，就将还留在树根上的军队排个序，再将树根的所有儿子中的仍然未有军队驻扎的点也排个序； 对这两个序列做比较，就可以判断出在该时间下，所有军队是否可以将疫情控制住

3.LCA；因为每一次二分后军队往上跳时，不就明显的是要用二分吗？

附上代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const int N=6e4;

int n,m,t,tot=0,atot=0,btot=0,ctot=0;
int d[N],query[N],f[N][20];
int ver[2*N],edge[2*N],Next[2*N],head[N];
bool ok,sta[N],need[N];
ll ans,tim[N],ned[N],dist[N][20];
pair<ll,int> h[N];
queue<int> q;

void add(int x,int y,int z){
    ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
}

void bfs(){
    q.push(1);
    d[1]=1;
    while(q.size()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i];
            if(d[y]) continue;
            d[y]=d[x]+1;
            f[y][0]=x,dist[y][0]=edge[i];
            for(int j=1;j<=21&&y-(1<<j)>=1;j++){
                f[y][j]=f[f[y][j-1]][j-1];
                dist[y][j]=dist[y][j-1]+dist[f[y][j-1]][j-1];
            }
            q.push(y);
        }
    }
}

bool dfs(int x){
    bool pson=0;
    if(sta[x]) return 1;
    for(int i=head[x];i;i=Next[i]){
        int y=ver[i];
        if(d[y]<d[x]) continue;
        pson=1;
        if(!dfs(y)) return 0;
    }
    if(!pson) return 0;
    return 1;
}

bool check(ll lim)
{
    memset(sta,0,sizeof(sta));
    memset(tim,0,sizeof(tim));
    memset(ned,0,sizeof(ned));
    memset(h,0,sizeof(h));
    memset(need,0,sizeof(need));
    atot=0,btot=0,ctot=0;
    for(int i=1;i<=m;i++){
        ll x=query[i],cnt=0;
        for(int j=t;j>=0;j--){
            if(f[x][j]>1&&cnt+dist[x][j]<=lim){
                cnt+=dist[x][j];
                x=f[x][j];
            }
        }
        if(f[x][0]==1&&cnt+dist[x][0]<=lim) h[++ctot]=make_pair(lim-cnt-dist[x][0],x);
        else sta[x]=1;
    }
    for(int i=head[1];i;i=Next[i]) if(!dfs(ver[i])) need[ver[i]]=1;
    sort(h+1,h+ctot+1);
    for(int i=1;i<=ctot;i++){
        if(need[h[i].second]&&h[i].first<dist[h[i].second][0]) need[h[i].second]=0;
        else tim[++atot]=h[i].first;//军队
    }
    for(int i=head[1];i;i=Next[i]) if(need[ver[i]]) ned[++btot]=dist[ver[i]][0];//节点距离 
    if(atot<btot) return 0;
    sort(tim+1,tim+atot+1);
	sort(ned+1,ned+btot+1);
    int i=1,j=1;
    while(i<=btot&&j<=atot){
        if(tim[j]>=ned[i]) i++,j++;
        else j++;
    }
    if(i>btot) return 1;
    return 0;
}

int main()
{
	ll l=0,r=0,mid;
    cin>>n;
    t=log2(n)+1;
    for(int i=1;i<n;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z),add(y,x,z);
        r+=z;
    }
    bfs();
    cin>>m;
    for(int i=1;i<=m;i++) scanf("%d",&query[i]);
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid)){
            r=mid-1;
            ans=mid;
            ok=true;
        }
        else l=mid+1;
    }
    if(!ok) cout<<-1;
    else cout<<ans;
    return 0;
}