疫情控制 [NOIP2012]

Description

H 国有 n 个城市，这 n 个城市用 n-1 条双向道路相互连通构成一棵树， 1 号城市是首都，也是树中的根节点。
H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，首都是不能建立检查点的。
现在，在 H 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度（单位：小时）。
请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。

Input

第一行一个整数 n，表示城市个数。
接下来的 n-1 行，每行 3 个整数，u、v、w，每两个整数之间用一个空格隔开，表示从城市 u 到城市 v 有一条长为 w 的道路。数据保证输入的是一棵树，且根节点编号为 1。
接下来一行一个整数 m，表示军队个数。
接下来一行 m 个整数，每两个整数之间用一个空格隔开，分别表示这 m 个军队所驻扎的城市的编号。

Output

共一行，包含一个整数，表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1。

Sample Input

4
1 2 1
1 3 2
3 4 3
2
2 2

Sample Output

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

思路

1.显而易见的性质：一个军队站得深度越小，产生的作用越大 (根节点除外)

　　-->尽量把点往上提 -->倍增优化

2.题目求的是时间中最长的最小值

　　-->最大/小的最小/大值常用二分答案

3.由于1中提到根节点不能放，所以以根节点的某个子节点为根的子树可能不能被覆盖

　　-->考虑子树间的军队移动

4.对于某个军队

　　如果最高不能到达根节点，根据性质1，设在能在的最高点

　　如果能到根节点，记录能继续走的距离（所有的从大到小排序）

5.扫描所有以根节点的某个子节点为根的子树，记录下没有被覆盖的子树（记录子树的根，也就是根的子节点i），按i到root的距离从大到小排序

6.对于每一个不能被覆盖的子树的根节点，如果子树中有能到达子树根节点的军队，根据贪心，选能继续走的距离最小的军队抵消（类似田忌赛马）

如果没有，拿继续走的距离最小的军队抵消（反正已经从大到小排好序了）

7.AC

代码

#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define RG register ll
#define rep(i,a,b)    for(RG i=a;i<=b;i++)
#define per(i,a,b)    for(RG i=a;i>=b;i--)
#define ll long long
#define inf (1<<30)
#define maxn 50005
using namespace std;
ll n,m,cnt,cnta,cntb;
ll head[maxn],st[maxn];
ll fa[maxn][21],dis[maxn][21];
ll minid[maxn],fumin[maxn],resmin[maxn];
bool vis[maxn],used[maxn];
struct E{
    ll v,next,val;
}e[maxn<<1];
struct Dat{
    ll id;ll res;
    inline bool operator < (const Dat &tmp)const{
        return res>tmp.res;
    }
}a[maxn],b[maxn];
inline ll read()
{
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

inline void add()
{
    RG u=read(),v=read(),val=read();
    e[++cnt].v=v,e[cnt].next=head[u],e[cnt].val=val,head[u]=cnt;swap(u,v);
    e[++cnt].v=v,e[cnt].next=head[u],e[cnt].val=val,head[u]=cnt;
}

void Pre_dfs(ll u,ll pa,ll val)
{
    fa[u][0]=pa,dis[u][0]=val;
    for(ll j=1;j<=20;j++)
        fa[u][j]=fa[fa[u][j-1]][j-1],dis[u][j]=dis[u][j-1]+dis[fa[u][j-1]][j-1];
    for(ll i=head[u];i;i=e[i].next)
        if(e[i].v!=pa)    Pre_dfs(e[i].v,u,e[i].val);
}

bool cover(ll u,ll pa)
{
    bool flg=1,leaf=1;
    if(vis[u])    return 1;
    for(ll i=head[u];i;i=e[i].next)
    {
        ll v=e[i].v;if(v==pa)    continue;
        leaf=0;
        if(!cover(v,u))
        {
            flg=0;
            if(u==1)    b[++cntb].id=v,b[cntb].res=e[i].val;
            else return 0;
        }
    }
    if(leaf)    return 0;
    return flg;
}

bool check(ll lim)
{
    memset(fumin,0,sizeof(fumin));
    memset(used,0,sizeof(used));
    memset(vis,0,sizeof(vis));
    cnta=cntb=0;
    rep(i,1,m)
    {
        ll x=st[i],cost=0;
        per(j,20,0)
            if(fa[x][j]>1&&cost+dis[x][j]<=lim)
                cost+=dis[x][j],x=fa[x][j];
        if(fa[x][0]==1&&cost+dis[x][0]<=lim)
        {
            a[++cnta].res=lim-dis[x][0]-cost;
            a[cnta].id=i;
            if(!fumin[x]||a[cnta].res<resmin[x])
                fumin[x]=i,resmin[x]=a[cnta].res;
        }
        else vis[x]=1;
    }
    if(cover(1,0))    return 1;
    sort(a+1,a+1+cnta);
    sort(b+1,b+1+cntb);
    ll now=1;used[0]=1;
    rep(i,1,cntb)
    {
        if(!used[fumin[b[i].id]])
            {used[fumin[b[i].id]]=1;continue;}
        while(now<=cnta&&(used[a[now].id]||a[now].res<b[i].res)) ++now;
        if(now>cnta)    return 0;
        used[a[now].id]=1;
    }
    return 1;
}

int main()
{
    n=read();
    rep(i,2,n)    add();
    m=read();
    rep(i,1,m)    st[i]=read();
    Pre_dfs(1,0,0);
    ll l=0,r=500000,mid,ans;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(mid))    ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<ans;
    return 0;
}

View Code