自动搬运

查看原文

来自洛谷，原作者为

	云浅知处 喵

搬运于2025-08-24 21:48:08，当前版本为作者最后更新于2022-01-17 21:01:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意大概是给定一棵树以及 $m$ 条路径，第 $i$ 条路径的权重为 $w_i$；要求选出来一些路径使得至少有一个点被覆盖了至少 $k$ 次，且使得这些路径的权重极差最小。

对于这种最小化极差的题有一个差不多的套路，就是将路径按照权重排序之后 2pointers。

具体来说，我们给树上的每个点都维护一个值表示它被覆盖的次数；每次加入一条路径就把路径上的点的覆盖次数都加一，删掉一条路径就把这些点都减一。存在一个点被覆盖了至少 $k$ 次就相当于所有点的权值中的最大值 $\ge k$。

用树剖维护链上加和全局最大值即可。时间复杂度 $O(n+m\log^2n)$。

#include<bits/stdc++.h>

using namespace std;

inline int read(){
    int x=0,f=1;char c=getchar();
    for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
    for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
    return x*f;
}

const int MN=2e5+5;
int n,m,k;
vector<int>G[MN];
pair<int,pair<int,int> >tr[MN];

int fa[MN],top[MN],hson[MN],dfn[MN],sz[MN],dep[MN];

int dfs1(int u,int de){
    sz[u]=1,dep[u]=de;
    for(int v:G[u]){
        if(v==fa[u])continue;
        fa[v]=u,sz[u]+=dfs1(v,de+1);
        if(sz[v]>sz[hson[u]])hson[u]=v;
    }
    return sz[u];
}

int tot=0;
void dfs2(int u,int tp){
    top[u]=tp,dfn[u]=++tot;
    if(hson[u])dfs2(hson[u],tp);
    for(int v:G[u]){
        if(v!=fa[u]&&v!=hson[u])dfs2(v,v);
    }
}

#define lson(o) (o<<1)
#define rson(o) (o<<1|1)

struct SegTree{
    int d[MN<<2],plz[MN<<2];
    
    inline void pushup(int o){
        d[o]=max(d[lson(o)],d[rson(o)]);
    }
    
    inline void clear(){
        memset(d,0,sizeof(d));
        memset(plz,0,sizeof(plz));
    }
    
    inline void pushdown(int ql,int qr,int o){
        if(plz[o]){
            d[lson(o)]+=plz[o],d[rson(o)]+=plz[o];
            plz[lson(o)]+=plz[o],plz[rson(o)]+=plz[o];
            plz[o]=0;
        }
    }
    
    inline void modify(int l,int r,int k,int ql,int qr,int o){
        if(l<=ql&&qr<=r){d[o]+=k,plz[o]+=k;return;}
        int mid=(ql+qr)>>1;pushdown(ql,qr,o);
        if(l<=mid)modify(l,r,k,ql,mid,lson(o));
        if(r>mid)modify(l,r,k,mid+1,qr,rson(o));
        pushup(o);
    }
    
    inline int query(){
        return d[1];
    }
}tree;

bool chk(){
    return tree.query()>=k;
}

void add(int u,int v,int w){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        tree.modify(dfn[top[u]],dfn[u],w,1,n,1);
        u=fa[top[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    tree.modify(dfn[u],dfn[v],w,1,n,1);
}

int dis(int u,int v){
	int res=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		res+=dfn[u]-dfn[top[u]]+1;
		u=fa[top[u]];
	}
	if(dep[u]>dep[v])swap(u,v);
	return res+dfn[v]-dfn[u]+1;
}

const int INF=2e9;

#define fi first
#define se second
#define OK puts("OK")

signed main(void){
	
#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
#endif		
    
    n=read(),m=read(),k=read();
    for(int i=1;i<=n-1;i++){
        int u=read(),v=read();
        G[u].push_back(v),G[v].push_back(u);
    }
    
    dfs1(1,1),dfs2(1,1),tree.clear(); 
    for(int i=1;i<=m;i++)tr[i].se.fi=read(),tr[i].se.se=read(),tr[i].fi=dis(tr[i].se.fi,tr[i].se.se);
    
    sort(tr+1,tr+m+1);
    
    int r=0,ans=INF;
    for(int l=1;l<=m;l++){
        while(!chk()){
        	r++;if(r>m){cout<<ans<<endl;return 0;}
			add(tr[r].se.fi,tr[r].se.se,1);
        }
        if(!chk())break;
        ans=min(ans,tr[r].fi-tr[l].fi);add(tr[l].se.fi,tr[l].se.se,-1);
    }
    
    cout<<((ans==INF)?-1:ans)<<endl;

    return 0;
}