Codeforces 983E - NN country（贪心+倍增优化）

一道（绝对）偏简单的 D1E，但是我怕自己过若干年（大雾）忘了自己的解法了，所以过来水篇题解（

首先考虑怎么暴力地解决这个问题，不难发现我们每一步肯定会贪心，贪心地跳到所有经过当前点的公交线路中另一端最浅的位置，直到到达两点的 \(\text{LCA}\) 为止。不难发现上述过程可以倍增优化，具体来说我们记 \(nxt_{i,j}\) 表示从 \(i\) 开始走 \(2^j\) 步最浅能够到达哪里，那么我们可以一面树剖求出经过每个点能够到达深度最浅的节点，一面倍增往上跳知道跳到深度 \(<\text{LCA}(u,v)\) 的位置为止。

不过上述算法有一个漏洞，就是在我们到达 \(\text{LCA}(u,v)\) 的前一步到达的点 \(u',v'\) 很可能已经可以通过某条公交线相连了，此时我们大可不必再花费 \(2\) 的代价跳到 \(\text{LCA}(u,v)\)，直接一步就可以搞定，答案需减一。因此考虑再倍增求出 \(u,v\) 到达 \(\text{LCA}(u,v)\) 之前上一步到达的节点 \(u',v'\)，不难发现，由于 \(u',v'\) 之间不存在祖先关系，因此 \(u',v'\) 存在公交线相连的充要条件是存在某个公交线，两个端点分别在 \(u',v'\) 子树内，这个可以 DFS 序+离线二维数点/在线主席树求出。

时间复杂度 \(n\log^2n\)，但显然有复杂度更优秀/更好写的 implementation，比方说树剖换成 set 启发式合并代码可以少三十多行，换成线段树合并可以少一个 \(\log\)。

我竟然写这么短的题解，我怕不是精神不正常（大雾

代码（这种题我都能码 171 行……zz 这题我实现得跟 sh*t 一样）：

const int MAXN=2e5;

const int LOG_N=18;

const int INF=0x3f3f3f3f;

int n,m,qu,qn,hd[MAXN+5],to[MAXN+5],nxt[MAXN+5],ec=0;

void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}

int siz[MAXN+5],wson[MAXN+5],dep[MAXN+5],fa[MAXN+5][LOG_N+2];

int top[MAXN+5],dfn[MAXN+5],tim=0,edt[MAXN+5];

void dfs1(int x){

	siz[x]=1;

	for(int e=hd[x];e;e=nxt[e]){

		int y=to[e];dep[y]=dep[x]+1;

		dfs1(y);siz[x]+=siz[y];

		if(siz[y]>siz[wson[x]]) wson[x]=y;

	}

}

void dfs2(int x,int tp){

	top[x]=tp;dfn[x]=++tim;if(wson[x]) dfs2(wson[x],tp);

	for(int e=hd[x];e;e=nxt[e]) if(to[e]!=fa[x][0]&&to[e]!=wson[x])

		dfs2(to[e],to[e]);

	edt[x]=tim;

}

int getlca(int x,int y){

	while(top[x]^top[y]){

		if(dep[top[x]]<dep[top[y]]) swap(x,y);

		x=fa[top[x]][0];

	} if(dep[x]<dep[y]) swap(x,y);

	return y;

}

struct node{int l,r,val,lz;} s[MAXN*4+5];

void pushup(int k){s[k].val=min(s[k<<1].val,s[k<<1|1].val);}

void build(int k,int l,int r){

	s[k].l=l;s[k].r=r;s[k].lz=INF;if(l==r) return s[k].val=INF,void();

	int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k);

}

void pushdown(int k){

	if(s[k].lz!=INF){

		chkmin(s[k<<1].val,s[k].lz);chkmin(s[k<<1|1].val,s[k].lz);

		chkmin(s[k<<1].lz,s[k].lz);chkmin(s[k<<1|1].lz,s[k].lz);

		s[k].lz=INF;

	}

}

void modify(int k,int l,int r,int x){

	if(l<=s[k].l&&s[k].r<=r){

		chkmin(s[k].val,x);chkmin(s[k].lz,x);

		return;

	} pushdown(k);int mid=s[k].l+s[k].r>>1;

	if(r<=mid) modify(k<<1,l,r,x);

	else if(l>mid) modify(k<<1|1,l,r,x);

	else modify(k<<1,l,mid,x),modify(k<<1|1,mid+1,r,x);

	pushup(k);

}

int query(int k,int x){

	if(s[k].l==s[k].r) return s[k].val;pushdown(k);

	pushdown(k);int mid=s[k].l+s[k].r>>1;

	if(x<=mid) return query(k<<1,x);

	else return query(k<<1|1,x);

}

void jumpath(int x,int y,int v){

	while(top[x]^top[y]){

		if(dep[top[x]]<dep[top[y]]) swap(x,y);

		modify(1,dfn[top[x]],dfn[x],v);

		x=fa[top[x]][0];

	} if(dep[x]<dep[y]) swap(x,y);

	modify(1,dfn[y],dfn[x],v);

}

int get_kanc(int x,int k){

	for(int i=LOG_N;~i;i--) if(k>>i&1) x=fa[x][i];

	return x;

}

int nt[MAXN+5][LOG_N+2],cnt[MAXN+5],ans[MAXN+5],mark[MAXN+5];

int step(int x,int d){

	if(dep[x]<=d) return 0;

	if(dep[nt[x][LOG_N]]>d) return -1;int cnt=0;

	for(int i=LOG_N;~i;i--) if(dep[nt[x][i]]>d) x=nt[x][i],cnt|=(1<<i);

	return cnt+(dep[x]>d);

}

int get_kstp(int x,int k){

	for(int i=LOG_N;~i;i--) if(k>>i&1) x=nt[x][i];

	return x;

}

vector<int> pts[MAXN+5];

struct qry{

	int x,y,t,id;

	bool operator <(const qry &rhs) const{

		return x<rhs.x;

	}

} q[MAXN*4+5];

void add_rec(int x1,int x2,int y1,int y2,int id){

//	printf("%d %d %d %d %d\n",x1,x2,y1,y2,id);

	q[++qn]={x2,y2,1,id};q[++qn]={x1-1,y2,-1,id};

	q[++qn]={x2,y1-1,-1,id};q[++qn]={x1-1,y1-1,1,id};

}

struct fenwick{

	int t[MAXN+5];

	void add(int x,int v){for(int i=x;i<=n;i+=(i&(-i))) t[i]+=v;}

	int query(int x){int ret=0;for(int i=x;i;i&=(i-1)) ret+=t[i];return ret;}

} tr;

int main(){

	scanf("%d",&n);

	for(int i=2;i<=n;i++) scanf("%d",&fa[i][0]),adde(fa[i][0],i);

	dfs1(1);dfs2(1,1);build(1,1,n);

	for(int i=1;i<=n;i++) modify(1,dfn[i],dfn[i],dep[i]);

	scanf("%d",&m);

	for(int i=1,x,y;i<=m;i++){

		scanf("%d%d",&x,&y);

		pts[dfn[x]].pb(dfn[y]);pts[dfn[y]].pb(dfn[x]);

//		printf("(%d %d)\n",dfn[x],dfn[y]);

		jumpath(x,y,dep[getlca(x,y)]);

	}

	for(int i=1;i<=LOG_N;i++) for(int j=1;j<=n;j++) fa[j][i]=fa[fa[j][i-1]][i-1];

	for(int i=1;i<=n;i++) nt[i][0]=get_kanc(i,dep[i]-query(1,dfn[i]));

	for(int i=1;i<=LOG_N;i++) for(int j=1;j<=n;j++) nt[j][i]=nt[nt[j][i-1]][i-1];

	scanf("%d",&qu);

	for(int i=1;i<=qu;i++){

		int x,y,l;scanf("%d%d",&x,&y);l=getlca(x,y);

		int sx=step(x,dep[l]),sy=step(y,dep[l]);

		if(!~sx||!~sy) ans[i]=-1;

		else{

			ans[i]=sx+sy;

			if(sx!=0&&sy!=0){

				int ax=get_kstp(x,sx-1);

				int ay=get_kstp(y,sy-1);

				add_rec(dfn[ax],edt[ax],dfn[ay],edt[ay],i);

			}

		}

	}

//	for(int i=1;i<=qu;i++) printf("%d\n",ans[i]);

	sort(q+1,q+qn+1);int cur=1;

	for(int i=1;i<=qn;i++){

		while(cur<=q[i].x){

			for(int y:pts[cur]) tr.add(y,1);

			cur++;

		} cnt[q[i].id]+=q[i].t*tr.query(q[i].y);

//		printf("%d %d %d\n",q[i].x,q[i].y,tr.query(q[i].y));

	}

	for(int i=1;i<=qu;i++) printf("%d\n",ans[i]-(cnt[i]>0));

	return 0;

}

巴特西

Codeforces 983E - NN country（贪心+倍增优化）

最新文章

热门文章