自动搬运

查看原文

来自洛谷，原作者为

	vectorwyx 打 OI 就像心跳一样自然，退役就像去世一样必然。

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

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

以下是正文

题意：给定一棵基环树森林，起初有 $m$ 个点已被选进 $S$ 里，你需要再选 $k$ 个点加入到 $S$ 中，最小化其余点到 $S$ 距离的最大值。

二分，树的部分同 P3523 做 dp。但是根结点（也就是在环上的点）的处理要保留，如果当前子树中最深的还未被覆盖的点距离根结点的距离为 $d$，它要求环上的某段区间 $[l,r]$ 里至少有一个点被选进 $S$ 里，然后最小化环上被选进 $S$ 的点数。这个问题和 P4155 的形式是一致的，断环成链后变为经典贪心，每次从还未被满足的区间中选一个右端点最靠左的区间，把它的右端点选进 $S$ 里。复杂度 $O(n^2\log n)$，通过倍增应该能优化到 $O(n\log^2 n)$，但是懒得写了。

代码如下：

#include<bits/stdc++.h>
namespace vectorwyx{
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define sml(x,y) (x=min(x,y))
#define big(x,y) (x=max(x,y))
#define ll long long
#define uint unsigned
#define ull unsigned long long
#define umap unordered_map
#define db double
#define fo(i,x,y) for(int i=(x);i<=(y);++i)
#define go(i,x,y) for(int i=(x);i>=(y);--i)
#define ptc putchar
#define emp emplace
#define re return
#define co continue
#define brk break
#define HH (ptc('\n'))
#define bctz __builtin_ctz
#define bclz __builtin_clz
#define bppc __builtin_popcount
using namespace std;
ll seed=chrono::system_clock::now().time_since_epoch().count();
mt19937 rnd(seed);
inline int rm(int x,int y){return (int)(rnd()%(y-x+1ll)+x);}
inline int read(){signed ch=getchar();int x=0,f=1;while(!isdigit(ch)){if(ch==(int)('-'))f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void out(int *a,int l,int r){fo(i,l,r) cout<<*(a+i)<<' ';puts("");}

//8:36~9:44~
const int N=105,inf=1e9;
int a[N],num,n,m,k,vis[N],ti,f[N],g[N],stk[N],top,ins[N],rk[N];
int mp[N][N];
vector<pii> e[N];

void dfs1(int x){
	if(vis[x]==ti) re;
	vis[x]=ti;
	for(auto i:e[x]) dfs1(i.fi);
}

struct Ctree{
int cir[N],ct,rvl[N],k,ins[N],ans,l[N],r[N],m,fl,nxt[N],sum[N],R[N];

void insert(int x){
	cir[++ct]=x;
	rk[x]=ct;ins[x]=1;
}
void play_it(){
	fo(i,1,ct-1) rvl[i]=rvl[i+ct]=mp[cir[i]][cir[i+1]];
	rvl[ct]=mp[cir[ct]][cir[1]];
	fo(i,1,ct) if(a[cir[i]]){fl=i;brk;}
	fo(i,1,2*ct-1) sum[i+1]=sum[i]+rvl[i];
//	cout<<"rvl:";out(rvl,1,2*ct);cout<<"sum:";out(sum,1,2*ct);
}

void dfs(int x,int fa){
	f[x]=0,g[x]=inf;
	for(auto i:e[x]) if(!ins[i.fi]&&i.fi!=fa){
		dfs(i.fi,x);
		big(f[x],f[i.fi]+i.se);
		sml(g[x],g[i.fi]+i.se);
	}
	if(a[x]) g[x]=0;
	if(f[x]+g[x]<=k) f[x]=-inf;
	if(f[x]+mp[x][fa]>k) f[x]=-inf,g[x]=0,ans++;//,printf("%d!\n",x); 
}

int solve(){
//	printf("solve(%d)\n",k);
	ans=m=0;
	fo(i,1,ct)
		dfs(cir[i],0);
//	printf("now ans=%d!\n",ans);
//	fo(i,1,ct) printf("%d:(%d,%d)\n",i,f[cir[i]],g[cir[i]]);
	int Fl=0;
	fo(i,1,2*ct) R[i]=inf;
	fo(i,1,ct){
		bool flg=0;
		fo(j,1,ct){
			int dis=abs(sum[i]-sum[j]);sml(dis,sum[ct+1]-dis);
			if(f[cir[i]]+g[cir[j]]+dis<=k){flg=1;brk;}
		}
		if(flg) co;
		int len=k-f[cir[i]];
//		printf("%d:len=%d\n",i,len);
		if(2*len>=sum[ct+1]){
//			puts("qwq");
			if(!fl) Fl=1;
			co;
		}
		++m;
		if(sum[i]+rvl[ct]>len){
			l[m]=1;r[m]=2*ct;
			go(j,i,1) if(sum[i]-sum[j]>len){l[m]=j+1;brk;}
			fo(j,i,2*ct) if(sum[j]-sum[i]>len){r[m]=j-1;brk;}
			if(r[m]>ct) co;
			l[m+1]=l[m]+ct;r[m+1]=r[m]+ct;
			++m;
		}else{
			l[m]=1;r[m]=2*ct;
			go(j,i+ct,1) if(sum[i+ct]-sum[j]>len){l[m]=j+1;brk;}
			fo(j,i+ct,2*ct) if(sum[j]-sum[i+ct]>len){r[m]=j-1;brk;}			
		}
	}
	if(!m) re ans+Fl;
//	fo(i,1,m) printf("[%d,%d]\n",l[i],r[i]);
	fo(i,1,m) sml(R[l[i]],r[i]);
	int c=0,mn=inf;
	go(i,2*ct,1){
		nxt[i]=mn;
		sml(mn,R[i]);
	}
	if(fl){
		int x=fl;
		while(nxt[x]<fl+ct){
			c++;
			x=nxt[x];
		}
	}else{
		c=inf;
		fo(i,1,ct){
			int x=i,rp=1;
			while(nxt[x]<i+ct){
				rp++;
				x=nxt[x];
			}
			sml(c,rp);
		}
	}
	big(c,Fl);
	re ans+c;
}
}tr[N];

bool dfs2(int x,int fa){
	stk[++top]=x;vis[x]=ti;
	bool fl=0;
	for(auto i:e[x]){
		if(vis[i.fi]==ti){//基环树找环一定要特判父亲！！
			if(i.fi==fa){
				if(!fl){
					fl=1;
					co;
				}	
			}
			do{
				tr[num].insert(stk[top]);
			}while(stk[top--]!=i.fi);
			re 1;
		}
		if(dfs2(i.fi,x)) re 1;
	}
	top--;
	re 0;
}

signed main(){
	cin>>n;int w=read();cin>>m;
	{
	int x[N];fo(i,1,n) x[i]=read()+1;
	fo(i,1,n) fo(j,1,n) mp[i][j]=inf;
	fo(i,1,n){
		int v=read();
		e[i].eb(x[i],v);
		e[x[i]].eb(i,v);
//		printf("%d <-> %d %d\n",i,x[i],v);
		sml(mp[i][x[i]],v);
		sml(mp[x[i]][i],v);
	}		
	}

	fo(i,1,w) a[read()+1]=1;
	fo(i,1,n) if(!vis[i]){
		++ti;++num;
		dfs1(i);
		++ti;
		dfs2(i,0);
		tr[num].play_it();
//		tr[i].rvl[tr[i].ct]=mp[tr[i]]
	}
//	tr[1].k=5;cout<<tr[1].solve()<<'\n';
//	tr[2].k=3;cout<<tr[2].solve()<<'\n';
//	re 0;
	int l=0,r=inf,mid,ans=inf;
	while(l<=r){
		mid=(l+r)>>1;
		int x=0;
		fo(i,1,num) tr[i].k=mid,x+=tr[i].solve();
		if(x>m) l=mid+1;
		else r=mid-1,ans=mid;
	}
	cout<<ans;
	return 0;
}
}
/*
-------------------------------------------------
*/










signed main(){re vectorwyx::main();}