题解：P12703 [KOI 2022 Round 2] 外环路

这题的图是 Halin Graph，树宽为

3

，可以构造 Halin Graph 树分解（code1），然后用逛公园一题树分解的做法解决（code2），复杂度

O(n\log n+q)

。

下面讲一点更 oi 的做法。

画图会发现这是一张平面图，由最外面的一个环（连起了所有叶子）和中间的一棵树组成。

对于这题，可以对树三度化，进行边分治。

对于树上被切开的两个连通块，两部分之间最多有三条边相连（环上两条边，一条树边）。

对于

O(1)

个这几条边上的点，作为起点跑一遍最短路，然后把当前的询问答案都 chkmin 一下。

跨越两边的询问不必再递归，在同一边的询问递归下去，每个询问最多被递归

\log

次。

复杂度

O(n\log^2 n+q\log n)

。

CPP

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define int long long
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 400005
#define inf 0x3f3f3f3f3f3f3f3f

int n,nn,m,res[maxn];
int qu[maxn],qv[maxn];
int fa[maxn];
vector<pii>G[maxn];

struct edge{
	int to,nxt,w;
}e[maxn<<1];
int tot=1,head[maxn];
void adde(int u,int v,int w){
	e[++tot]=(edge){v,head[u],w};
	head[u]=tot;
}
void add(int u,int v,int w){
	adde(u,v,w);
	adde(v,u,w);
}

void rebuild(int u,int pa){
	int lst=u;
	for(auto it:G[u]){
		int v=it.fi,w=it.se; 
		if(v==pa)continue;
		rebuild(v,u);
		add(lst,++nn,0),add(nn,v,w);
		lst=nn;
	}
}

vector<pii>go[maxn];

#define iter(i,u,v,w) for(int i=head[u],v=e[i].to,w=e[i].w;i;i=e[i].nxt,v=e[i].to,w=e[i].w)

int allsz,mn,id,sz[maxn];
bool vis[maxn<<1];
void gete(int u,int pa){
	sz[u]=1;
	iter(i,u,v,w){
		if(v==pa || vis[i])continue;
		gete(v,u); sz[u]+=sz[v];
		if(mn>max(sz[v],allsz-sz[v])) mn=max(sz[v],allsz-sz[v]),id=i;
	}
}

int col[maxn];
int st[maxn],top;

namespace D{

struct edge{
	int to,nxt,w;
}e[maxn<<1];
int tot,head[maxn];
void adde(int u,int v,int w){
	e[++tot]=(edge){v,head[u],w};
	head[u]=tot;
}
bool vis[maxn];
void dij(int u,int*dis){
	For(i,1,top) vis[st[i]]=0,dis[st[i]]=inf;
	dis[u]=0;
	priority_queue<pii,vector<pii>,greater<pii>>q;
	q.push(mkp(0,u));
	while(q.size()){
		int u=q.top().se;q.pop();
		if(vis[u])continue; vis[u]=1;
		iter(i,u,v,w){
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(mkp(dis[v],v));
			}
		}
	}
}

}

void color(int u,int pa,int c){
	col[u]=c;
	st[++top]=u;
	iter(i,u,v,w)if(!vis[i]&&v!=pa)color(v,u,c);
}


pii tmp[999]; int len,tw[999];
int dis[9][maxn];
void clear(){
	For(i,1,top){
		int u=st[i];
		col[u]=0; D::head[u]=0;
	}top=0; D::tot=0; len=0;
}

void solve(int u,vi qs){
	if(allsz==1||!qs.size())return;
	mn=inf,gete(u,0);
	int x=e[id].to,y=e[id^1].to;
	vis[id]=vis[id^1]=1;
	vi qx,qy;
	color(x,0,1);
	color(y,0,2);
	For(i,1,top){
		int u=st[i];
		iter(i,u,v,w){
			if(!col[v])continue;
			D::adde(u,v,w);
			if(col[u]==1&&col[v]==2) tmp[++len]=mkp(u,v),tw[len]=w,assert(len<=3);
		}
		for(auto it:go[u]){
			int v=it.fi,w=it.se;
			if(!col[v])continue;
			D::adde(u,v,w);
			if(col[u]==1&&col[v]==2) tmp[++len]=mkp(u,v),tw[len]=w,assert(len<=3);
		}
	}
	assert(len<=3);
	For(i,1,len){
		D::dij(tmp[i].fi,dis[i*2-1]);
		D::dij(tmp[i].se,dis[i*2]);
	}
	for(auto it:qs){
		int u=qu[it],v=qv[it];
		if(col[u]>col[v])swap(u,v);
		if(col[u]!=col[v]){
			For(i,1,len){
				res[it]=min(res[it],dis[i*2-1][u]+dis[i*2][v]+tw[i]);
			}
		}else{
			if(col[u]==1){
				For(i,1,len) res[it]=min(res[it],dis[i*2-1][u]+dis[i*2-1][v]);
				qx.pb(it);
			}else{
				For(i,1,len) res[it]=min(res[it],dis[i*2][u]+dis[i*2][v]);
				qy.pb(it);
			}
		}
	}
	clear();
	allsz=sz[x],solve(x,qx);
	allsz=sz[y],solve(y,qy);
}

int leaf[maxn],lcnt;

signed main()
{
	n=read();nn=n;
	For(i,2,n){
		fa[i]=read(); int w=read();
		G[i].pb(mkp(fa[i],w));
		G[fa[i]].pb(mkp(i,w));
	}
	For(i,1,n) if(G[i].size()==1) leaf[lcnt++]=i;
	For(i,0,lcnt-1){
		int u=leaf[i],v=leaf[(i+1)%lcnt];
		int w=read();
		go[u].pb(mkp(v,w)),go[v].pb(mkp(u,w));
	}
	rebuild(1,0);
	allsz=nn;
	vi orz;
	m=read();
	For(i,1,m){
		qu[i]=read(),qv[i]=read();
		orz.pb(i);
		res[i]=inf;
	}
	solve(1,orz);
	For(i,1,m){
		printf("%lld\n",res[i]);
	}
	return 0;
}

题解：P12703 [KOI 2022 Round 2] 外环路

文章操作

相关推荐

评论

题解：P12703 [KOI 2022 Round 2] 外环路