[NOIP2012]疫情控制

题目

题目描述

$H$ 国有 $n$ 个城市，这 $n$ 个城市用 $n-1$ 条双向道路相互连通构成一棵树，$1$ 号城市是首都，也是树中的根节点。

$H$ 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，首都是不能建立检查点的。

现在，在 $H$ 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度（单位：小时）。

请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。

输入输出格式

输入格式：

第一行一个整数 $n$，表示城市个数。

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

接下来一行一个整数 $m$，表示军队个数。

接下来一行 $m$ 个整数，每两个整数之间用一个空格隔开，分别表示这 $m$ 个军队所驻扎的城市的编号。

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

说明

【输入输出样例说明】

第一支军队在 $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 提高组第二天第三题

题解

可以发现答案具有单调性，所以可以二分答案

根据贪心的思想，军队到达的点越靠近根节点控制的范围越大，所以军队肯定向上走，向上走用倍增优化

分两种情况：

军队在二分的时间内走不到根节点，这时候最优的情况肯定是在能到达的最靠近根节点的地方建立检查站
军队在二分的时间内能走到根节点，说明ta能跨过根节点建立检查站

对于第二类要特殊处理，还是贪心的思想，军队到达根节点剩余的时间越少，ta建立检查站的地方就应该越靠近根节点

同时如果ta能跨过根节点，但是ta上来的那个子树没控制，应该优先控制自己上来的子树

所以军队按剩余时间排序，子树按到根节点的距离排序，注意细节就行了qwq

代码

# include<iostream>
# include<cstdio>
# include<cstring>
# include<algorithm>
# define LL long long
using namespace std;
struct p{
    LL x,y,dis;
}c[100001];
struct q{
    LL i,rest;
}a1[50001],a2[50001];
LL n,m,num,s,ss;
LL h[50001],army[50001],re[50001],kk[50001];
LL f[50001][22],d[50001][22];
bool use[50001],vis[50001];
bool cmp(q a,q b)
{
    return a.rest>b.rest;
}
LL read()
{
    LL x=0;
    char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=x*10+ch-48,ch=getchar();
    return x;
}
void add(LL x,LL y,LL dis)
{
    c[++num].x=h[x],c[num].y=y,c[num].dis=dis,h[x]=num;
}
void dfs(LL x,LL fa,LL t)
{
    f[x][0]=fa,d[x][0]=t;
    for(int i=h[x];i;i=c[i].x)
      {
        int tt=c[i].y;
        if(tt==fa) continue;
        dfs(tt,x,c[i].dis);
      }
}
void init()
{
    for(int i=1;i<=17;++i)
      for(int j=1;j<=n;++j)
        f[j][i]=f[f[j][i-1]][i-1],d[j][i]=d[j][i-1]+d[f[j][i-1]][i-1];
}
bool find(LL x,LL fa)
{
    if(vis[x]) return 1;
    bool ff=0,fff=1;
    for(int i=h[x];i;i=c[i].x)
      {
        int tt=c[i].y;
        if(tt==fa) continue;
        ff=1;
        if(!find(tt,x))
        {
		  	fff=0;
            if(x==1) a2[++ss].i=tt,a2[ss].rest=c[i].dis;
            else return 0;
        }
      }
    if(!ff) return 0;
    return fff;
}
bool look(LL t)
{
    s=0,ss=0;
    memset(use,0,sizeof(use));
    memset(vis,0,sizeof(vis));
    memset(re,0,sizeof(re));
    memset(kk,0,sizeof(kk));
    for(int i=1;i<=m;++i)
      {
        LL x=army[i],nu=0;
        for(int j=17;j>=0;--j)
          if(f[x][j]&&f[x][j]!=1&&nu+d[x][j]<=t) nu+=d[x][j],x=f[x][j];
        if(f[x][0]==1&&nu+d[x][0]<=t)
        {
            a1[++s].rest=t-nu-d[x][0];
            a1[s].i=i;
            if(!re[x]||a1[s].rest<re[x])
            re[x]=a1[s].rest,kk[x]=i;
        }
        else vis[x]=1;
      }
    if(find(1,0)) return 1;
    sort(a1+1,a1+1+s,cmp),sort(a2+1,a2+1+ss,cmp);
    LL fr=1;
    use[0]=1;
    for(int i=1;i<=ss;++i)
      {
        if(!use[kk[a2[i].i]])
        {
            use[kk[a2[i].i]]=1;
            continue;
        }
        while(fr<=s&&(use[a1[fr].i]||a1[fr].rest<a2[i].rest)) ++fr;
        if(fr>s) return 0;
        use[a1[fr].i]=1;
      }
    return 1;
}
int main()
{
    n=read();
    for(int i=1;i<n;++i)
      {
        LL x=read(),y=read(),dis=read();
        add(x,y,dis),add(y,x,dis);
      }
    dfs(1,0,0),init();
    m=read();
    for(int i=1;i<=m;++i)
      army[i]=read();
    LL l=0,r=1e7,ans=-1;
    while(l<=r)
    {
        LL mid(l+r>>1);
        if(look(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%lld",ans);
    return 0;
}

题目