专栏文章

题解：P1084 [NOIP 2012 提高组] 疫情控制

WWei_Han
P1084题解参与者 5已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@mipdgvxw
此快照首次捕获于
2025/12/03 10:12
3 个月前
此快照最后确认于
2025/12/03 10:12
3 个月前
查看原文
有些坑点的题。
答案的单调性显然，考虑二分答案，首先能够发现向父亲走一定不劣，因为覆盖的节点更多了，那么我们已知最大时间为 kk，令每一个点向上走尽量接近 kk 的距离就好了，可是由于不能走到根，那么有的点可能还有剩余步数，但是只能暂时停在根的儿子下。
这样我们就能够得到一棵新树，如果一个被染色点不在根的儿子，那么其一定无法再移动了，所以我们之后的操作只需要对于根的儿子讨论即可。
对于新树，根有的子树内是覆盖不完整的，称为空子树，那么我们需要拿有多余点的子树去填空子树，一个很 naive 的想法是开两个小根堆，分别存空的和多余的到根的距离，匹配一下就做完了，这样确实挺对的，但只有 7070 分。
考虑上述做法错在哪里，假设此时有根有三个儿子，a,b,ca,b,c，其中 cc 为空，a,ba,b 均有一个染色点，其中距离 b<a<cb < a < c，我们需要填满 cc，那么刚才的做法可能是直接让 aa 去 cc，花费时间为 a+ca+c，而另一种做法是先让 aa 去 bb，再让 bb 去 cc，时间为 max⁡(a+b,b+c)\max(a+b,b+c)，在某些情况下是更优的。
讨论区一组直观的数据：
CPP
4
1 2 99
1 3 1
1 4 99
3
3 4 4
答案为 100100。
因此，我们考虑优先将所有距离够的染色点提到根，对于来自于每一棵子树的点按照剩余步数排序，那么剩余步数多的肯定更加可能走到更远的未染色点，那么我们就要将距离短的放回本子树中保证子树被染色，放一个就好了，具体实现可以参考代码。
复杂度 O(nlog⁡2n)O(n\log^2 n)，因某些不可名状因素，采用树剖实现。
7070 分实现：
CPP
const ll N=1e6+5,M=2e4+5;
ll n,m,fa[N],siz[N],id[N],w[N],son[N],dep[N],top[N],cnt,dis[N],Siz[N],vis[N];
vector<pii> g[N],E;vector<ll> P;
inline void dfs1(ll x,ll fat,ll depth){dep[x]=depth,siz[x]=1,fa[x]=fat;for(auto [y,w]:g[x]){if(y==fat) continue;dis[y]=dis[x]+w;dfs1(y,x,depth+1);siz[x]+=siz[y];if(siz[y]>siz[son[x]]) son[x]=y;}}
inline void dfs2(ll x,ll nowtop){top[x]=nowtop,id[x]=++cnt,w[cnt]=x;if(!son[x])return;dfs2(son[x],nowtop);for(auto [y,w]:g[x])if(y!=fa[x]&&y!=son[x]) dfs2(y,y);}
inline ll LCA(ll x,ll y){while(top[x]^top[y]) dep[top[x]]<dep[top[y]]?y=fa[top[y]]:x=fa[top[x]];return dep[x]<dep[y]?x:y;}
inline ll DIS(ll x,ll y){return dis[x]+dis[y]-2*dis[LCA(x,y)];}
inline ll LCApre(ll x,ll y){ll lst=x;while(top[x]^top[y]) dep[top[x]]<dep[top[y]]?lst=top[y],y=fa[top[y]]:lst=top[x],x=fa[top[x]];if(dep[x]<dep[y]) swap(x,y);return x==y?lst:w[id[y]+1];}
inline ll ask_chain(ll x,ll pre,ll mid)
{
    ll xx=x,y=pre;
    while(top[x]^top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        ll Top=max(id[pre],id[top[x]]);Top=w[Top];
        if(dis[xx]-dis[Top]<mid){x=fa[top[x]];continue;}
        ll l=id[Top],r=id[x];
        while(l<r)
        {
            ll mid=l+r+1>>1;
            if(dis[xx]-dis[w[mid]]<mid) r=mid-1;
            else l=mid;
        }
        return w[l];
    }
    if(dep[x]<dep[y]) swap(x,y);
    ll l=id[y],r=id[x];
    while(l<r)
    {
        ll mid=l+r+1>>1;
        if(dis[xx]-dis[w[mid]]<mid) r=mid-1;
        else l=mid;
    }
    return w[l];
}
inline ll dfs3(ll x)
{
    ll sum=0;for(auto [y,w]:g[x]) if(y!=fa[x]) sum+=dfs3(y);
    return (g[x].size()!=1&&sum==g[x].size()-1)||(Siz[x]>0);
}
inline ll dfs4(ll x)
{
    ll sum=0;for(auto [y,w]:g[x]) if(y!=fa[x]) sum+=dfs3(y);
    return (g[x].size()!=1&&sum==g[x].size()-1);
}
inline bool check(ll mid)
{
    priority_queue<pii,vector<pii>,greater<pii> > pq;
    fo(0,i,n+1) Siz[i]=0,vis[i]=0;
    for(ll i:P)
    {
        ll pre=LCApre(i,1);
        if(dis[i]-dis[pre]<=mid) Siz[pre]++;
        else Siz[ask_chain(i,pre,mid)]++;
        if(dis[i]-dis[1]<=mid) pq.push(mp(mid-dis[i]+dis[1],pre));
    }
    for(auto [y,w]:g[1]) if(Siz[y]) vis[y]=dfs4(y);E.clear();
    for(auto [y,w]:g[1]) if(!dfs3(y)) E.pb(mp(dis[y],y));sort(all(E));
    ll ans=0;
    for(auto [w,i]:E)
    {
        while(pq.size()&&(pq.top().fi<w||(!vis[pq.top().se]&&Siz[pq.top().se]<=1))) pq.pop();
        if(pq.size())
        {
            Siz[pq.top().se]--,pq.pop(),ans++;
        }
    }
    return ans==E.size();
}
signed main(){
    read(n);ll u,v,w;
    fo(1,i,n-1) read(u,v,w),g[u].pb(mp(v,w)),g[v].pb(mp(u,w));
    dfs1(1,0,1),dfs2(1,1);
    ll maxn=0,maxx=0;fo(1,i,n) if(dis[i]>=maxn) maxx=maxn,maxn=max(maxn,dis[i]);else if(dis[i]>=maxx) maxx=dis[i];
    read(m);fo(1,i,m) read(u),P.pb(u);
    ll l=0,r=1e14; 
    while(l<r)
    {
        ll mid=l+r>>1;
        ll opt=check(mid);
        if(opt) r=mid;
        else l=mid+1;
    }
    wr(l==1e14?-1:l),pr;
    return 0;
}
满分，区别只有 check 函数:
CPP
const ll N=1e6+5,M=2e4+5;
ll n,m,fa[N],siz[N],id[N],w[N],son[N],dep[N],top[N],cnt,dis[N],Siz[N],vis[N];
vector<pii> g[N],E;vector<ll> P;
inline void dfs1(ll x,ll fat,ll depth){dep[x]=depth,siz[x]=1,fa[x]=fat;for(auto [y,w]:g[x]){if(y==fat) continue;dis[y]=dis[x]+w;dfs1(y,x,depth+1);siz[x]+=siz[y];if(siz[y]>siz[son[x]]) son[x]=y;}}
inline void dfs2(ll x,ll nowtop){top[x]=nowtop,id[x]=++cnt,w[cnt]=x;if(!son[x])return;dfs2(son[x],nowtop);for(auto [y,w]:g[x])if(y!=fa[x]&&y!=son[x]) dfs2(y,y);}
inline ll LCA(ll x,ll y){while(top[x]^top[y]) dep[top[x]]<dep[top[y]]?y=fa[top[y]]:x=fa[top[x]];return dep[x]<dep[y]?x:y;}
inline ll LCApre(ll x,ll y){ll lst=x;while(top[x]^top[y]) dep[top[x]]<dep[top[y]]?lst=top[y],y=fa[top[y]]:lst=top[x],x=fa[top[x]];if(dep[x]<dep[y]) swap(x,y);return x==y?lst:w[id[y]+1];}
inline ll ask_chain(ll x,ll pre,ll mid)
{
    ll xx=x,y=pre;
    while(top[x]^top[y])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        ll Top=max(id[pre],id[top[x]]);Top=w[Top];
        if(dis[xx]-dis[Top]<mid){x=fa[top[x]];continue;}
        ll l=id[Top],r=id[x];
        while(l<r)
        {
            ll mid=l+r+1>>1;
            if(dis[xx]-dis[w[mid]]<mid) r=mid-1;
            else l=mid;
        }
        return w[l];
    }
    if(dep[x]<dep[y]) swap(x,y);
    ll l=id[y],r=id[x];
    while(l<r)
    {
        ll mid=l+r+1>>1;
        if(dis[xx]-dis[w[mid]]<mid) r=mid-1;
        else l=mid;
    }
    return w[l];
}
inline ll dfs3(ll x)
{
    ll sum=0;for(auto [y,w]:g[x]) if(y!=fa[x]) sum+=dfs3(y);
    return (g[x].size()!=1&&sum==g[x].size()-1)||(Siz[x]>0);
}
inline ll dfs4(ll x)
{
    ll sum=0;for(auto [y,w]:g[x]) if(y!=fa[x]) sum+=dfs3(y);
    return (g[x].size()!=1&&sum==g[x].size()-1);
}
inline bool check(ll mid)
{
    priority_queue<pii,vector<pii>,greater<pii> > pq;
    fo(0,i,n+1) Siz[i]=0,vis[i]=0;ll ans=0;
    vector<pii> E1,E2;
    for(ll i:P)
    {
        ll pre=LCApre(i,1);
        if(dis[i]-dis[pre]<=mid) E1.eb(mp(mid-dis[i]+dis[1],pre));
        else Siz[ask_chain(i,pre,mid)]=1;
    }
    for(auto [y,w]:g[1]) Siz[y]=dfs4(y);
    sort(all(E1));for(auto [w,i]:E1)if(w>0&&(Siz[i]||w>=dis[i])) pq.push(mp(w,i));else Siz[i]=1;
    E.clear();for(auto [y,w]:g[1]) if(!dfs3(y)) E.pb(mp(dis[y],y));sort(all(E));
    for(auto [w,i]:E)
    {
        while(pq.size()&&(pq.top().fi<w)) pq.pop();
        if(pq.size()) Siz[pq.top().se]--,pq.pop(),ans++;
    }
    return ans==E.size();
}
signed main(){
    read(n);ll u,v,w;
    fo(1,i,n-1) read(u,v,w),g[u].pb(mp(v,w)),g[v].pb(mp(u,w));
    read(m);fo(1,i,m) read(u),P.pb(u);
    dfs1(1,0,1),dfs2(1,1);
    ll l=0,r=1e14; 
    while(l<r)
    {
        ll mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    wr(l==1e14?-1:l),pr;
    return 0;
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...