[NOIp2012]疫情控制题解

好久没更，强迫自己写一篇。
~~神 tm 大预言家出的题~~

注意到如果 (x) 小时可以控制住疫情，则 (forall x'>x) 必然也可以控制住疫情，显然答案具有单调性，可以二分答案。
考虑对于当前二分到的答案 (mid) 如何 check。根据贪心的策略，我们需要让所有军队的深度尽量小，于是可以考虑每一支军队向上跳的过程，这一步可以通过倍增预处理在 (log) 时间实现。
对于在 (mid) 时间内无论如何也跳不到根的子节点的军队，就原地（指最后跳到的地方）驻扎，答案最优。
对于跳至根的子节点后仍有剩余时间的军队 (s)，分成两种情况：

如果剩余时间不能使其在根节点之间跳一个往返，即剩余时间小于 (2 imes dis(s,root)) 的军队，原地驻扎。
反之，将符合此条件的所有军队按照剩余时间排序，并将还未控制住疫情的根的子节点按照距根的距离排序，用双指针将军队与城市一一进行匹配。

考虑这么贪心做的正确性，对于剩余时间不够的军队，如果选择跳过树根去另一个子节点 (s') 驻扎，则必然 (dis(root,s)>dis(root,s'))，这么做可能会导致需要一个剩余时间足够的军队 (s'') 从其本来位置跨过根跳至 (s)，花费时间 (dis(root,s'')+dis(root,s))，而这样做花的时间显然比 (s) 原地驻扎，(s'') 跨过根跳至 (s') 的情况长，于是贪心策略正确。
当然，也有可能存在一个军队剩余时间不够，但是其子树已被另一个军队控制的情况，那么这个军队就应算入到上文的第二种情况中。
具体实现较为麻烦，可以根据个人编码习惯写，这里不想再赘述。

#include <bits/stdc++.h>
#define mem(a) memset(a,0,sizeof(a))
#define st first
#define nd second
using namespace std;
typedef long long ll;

const int N=5e4+5;
struct Edge{int to,nxt,w;}e[N<<1];
int head[N],n,m,cnt,fa[N][18],sod[N],dep[N];
ll dis[N],ans,mch[N],mch2[N];
bool fl,stay[N],mst[N];
pair<ll,int> h[N];

inline void add(int u,int v,int w) {e[++cnt]=(Edge){v,head[u],w};head[u]=cnt;}

void dfs0(int u,int fat)
{
    fa[u][0]=fat; dep[u]=dep[fat]+1;
    for(int i=1;(1<<i)<=dep[u];++i)
        fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[u],v;i;i=e[i].nxt)
    {
        v=e[i].to; if(v==fat) continue;
        dis[v]=dis[u]+e[i].w;
        dfs0(v,u);
    }
}

bool dfs(int u)
{
    if(stay[u]) return 1;
    bool hasSon=0;
    for(int i=head[u],v;i;i=e[i].nxt)
    {
        v=e[i].to; if(v==fa[u][0]) continue;
        hasSon=1;
        if(!dfs(v)) return 0;
    }
    return hasSon;
}

bool check(ll lim)
{
    mem(stay); mem(mch);
    mem(mch2); mem(h); mem(mst);
    int toth=0,tota=0,totb=0;
    for(int i=1;i<=m;++i)
    {
        ll sum=0; int x=sod[i];
        for(int j=log2(dep[x]);~j;--j)
            if(fa[x][j]>1&&sum+dis[x]-dis[fa[x][j]]<=lim)
                sum+=dis[x]-dis[fa[x][j]],x=fa[x][j];
        if(fa[x][0]==1&&sum+dis[x]<=lim) h[++toth]={lim-sum-dis[x],x};
        else stay[x]=1;
    }
    for(int i=head[1];i;i=e[i].nxt)
        if(!dfs(e[i].to)) mst[e[i].to]=1;
    for(int i=1;i<=toth;++i)
        if(mst[h[i].nd]&&h[i].st<dis[h[i].nd]) mst[h[i].nd]=0;
        else mch[++tota]=h[i].st;
    for(int i=head[1];i;i=e[i].nxt)
        if(mst[e[i].to]) mch2[++totb]=dis[e[i].to];
    if(tota<totb) return 0;
    sort(mch+1,mch+tota+1);
    sort(mch2+1,mch2+totb+1);
    int i=1,j=1;
    while(i<=tota&&j<=totb)
        if(mch[i]>=mch2[j]) ++i,++j;
        else ++i;
    return j>totb;
}

int main()
{
    scanf("%d",&n); ll sum=0;
    for(int i=1,a,b,c;i<n;++i)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c); add(b,a,c);
        sum+=c;
    }
    dfs0(1,0);
    scanf("%d",&m);
    for(int i=1;i<=m;++i) scanf("%d",&sod[i]);
    ll l=0,r=sum;
    while(l<=r)
    {
        ll mid=l+r>>1;
        if(check(mid)) ans=mid,r=mid-1,fl=1;
        else l=mid+1;
    }
    printf("%lld",fl?ans:-1);
    return 0;
}

[NOIp2012]疫情控制 题解

[NOIp2012]疫情控制题解