差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:基环树 [2021/07/16 19:18]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:基环树 [2021/07/17 09:26] (当前版本)
jxm2001 [例题四]
@@ 行 163: / 行 163: @@
 === 题意 ===
-题目大意就省略了，大概就是给定基环树森林，求所有基环树的直径之和。
+题目大意就省略了，大概就是给定基环树森林，求所有基环树的最长路径之和。(注意最长路径 $\neq$ 直径)
 === 题解 ===
@@ 行 256: / 行 256: @@
 	}
 	enter(ans);
+	return 0;
+}
+</code>
+</hidden>
+==== 例题四 ====
+[[https://www.luogu.com.cn/problem/P1399|洛谷p1399]]
+=== 题意 ===
+给定一个基环树，要求在图上找到一个点，使得该点到其他点的最大距离最小。(该点可以在边上的某个位置)
+=== 题解 ===
+显然答案是基环树的直径除以 $2$，至于基环树的直径，首先子树贡献同基环树的最长路径，但环上点对 $(u,v)$ 的贡献改为
+$$
+\min(d(u)+d(v)+\text{dis}(u,v),d(u)+d(v)+s-\text{dis}(u,v))
+$$
+考虑依次断开一条边，得到链后计算 $\max(d(u)+d(v)+\text{dis}(u,v))$ 得到生成树的直径，则所有断边情况中的最小值就是基环树的直径。
+简短证明一下上述结论：首先任意断开一条环上的边可以得到一棵生成树，显然生成树的直径不小于基环树的直径。
+事实上，取基环树直径的中点 $rt$，做 $rt$ 的最短路生成树，则最短路生成树的直径等于基环树的直径。证毕。
+但这样时间复杂度是 $O(n^2)$，考虑优化。记环上的点分别为 $u_1,u_2\cdots u_m$，考虑先断开 $(u_1,u_m)$ 边，求出前缀
+$$
+\text{pre1}(i)=\max_{1\le j\le i}(d(u_j)+\text{dis}(u_j,u_1))\\
+\text{pre2}(i)=\max_{1\le j,k\le i}(d(u_j)+d(u_k)+\text{dis}(u_j,u_k))
+$$
+类似定义后缀 $\text{suf1}(i),\text{suf2}(i)$，于是断开 $(u_1,u_m)$ 边的贡献为 $\text{pre2}(k)$。
+接下来考虑断开 $(u_i,u_{i-1})$ 的边，分 $(u\lt i,v\ge i),(u,v\lt i),(u,v\ge i)$ 三种情况讨论，此时贡献为
+$$
+\max\left(\text{pre1}(i-1)+\text{suf1}(i)+\text{dis}(u_{i-1},u_i),\max(\text{pre2}(i-1),\text{suf2}(i))\right)
+$$
+总时间复杂度 $O(n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5;
+const LL inf=1e16;
+struct Edge{
+	int to,w,id,next;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v,int w,int id){
+	edge[++edge_cnt]=Edge{v,w,id,head[u]};
+	head[u]=edge_cnt;
+}
+bool edge_vis[MAXN],node_vis[MAXN],node_cyc[MAXN];
+LL d[MAXN],cyc_len;
+vector<int> cyc;
+bool dfs1(int u,LL dep){
+	if(node_vis[u]){
+		cyc_len=dep-d[u];
+		cyc.push_back(u);
+		return node_cyc[u]=true;
+	}
+	d[u]=dep;
+	node_vis[u]=true;
+	bool flag=false;
+	for(int i=head[u];i;i=edge[i].next){
+		if(edge_vis[edge[i].id])continue;
+		edge_vis[edge[i].id]=true;
+		int v=edge[i].to;
+		if(dfs1(v,dep+edge[i].w)&&!node_cyc[u]){
+			cyc.push_back(u);
+			node_cyc[u]=true;
+			flag=true;
+		}
+	}
+	return flag;
+}
+LL dfs2(int u,int fa){
+	LL ans=0;
+	d[u]=0;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa||node_cyc[v])continue;
+		ans=max(ans,dfs2(v,u));
+		ans=max(ans,d[u]+d[v]+edge[i].w);
+		d[u]=max(d[u],d[v]+edge[i].w);
+	}
+	return ans;
+}
+LL pre[MAXN],suf[MAXN],pre1[MAXN],pre2[MAXN],suf1[MAXN],suf2[MAXN];
+LL solve(int u){
+	cyc.clear();
+	dfs1(u,0);
+	for(int i=1,j=cyc.size()-1;i<j;i++,j--)swap(cyc[i],cyc[j]);
+	_for(i,0,cyc.size()){
+		pre[cyc[i]]=d[cyc[i]]-d[cyc[0]];
+		suf[cyc[i]]=d[cyc[cyc.size()-1]]-d[cyc[i]];
+	}
+	LL w0=cyc_len-d[cyc[cyc.size()-1]];
+	LL ans1=0,pre_t=-inf,suf_t=-inf;
+	_for(i,0,cyc.size())ans1=max(ans1,dfs2(cyc[i],0));
+	_for(i,0,cyc.size()){
+		pre1[cyc[i]]=d[cyc[i]]+pre[cyc[i]];
+		pre2[cyc[i]]=d[cyc[i]]+pre[cyc[i]]+pre_t;
+		pre_t=max(pre_t,d[cyc[i]]-pre[cyc[i]]);
+	}
+	_for(i,1,cyc.size()){
+		pre1[cyc[i]]=max(pre1[cyc[i]],pre1[cyc[i-1]]);
+		pre2[cyc[i]]=max(pre2[cyc[i]],pre2[cyc[i-1]]);
+	}
+	for(int i=cyc.size()-1;i>=0;i--){
+		suf1[cyc[i]]=d[cyc[i]]+suf[cyc[i]];
+		suf2[cyc[i]]=d[cyc[i]]+suf[cyc[i]]+suf_t;
+		suf_t=max(suf_t,d[cyc[i]]-suf[cyc[i]]);
+	}
+	for(int i=cyc.size()-2;i>=0;i--){
+		suf1[cyc[i]]=max(suf1[cyc[i]],suf1[cyc[i+1]]);
+		suf2[cyc[i]]=max(suf2[cyc[i]],suf2[cyc[i+1]]);
+	}
+	LL ans2=pre2[cyc[cyc.size()-1]];
+	_for(i,1,cyc.size())
+	ans2=min(ans2,max(pre1[cyc[i-1]]+w0+suf1[cyc[i]],max(pre2[cyc[i-1]],suf2[cyc[i]])));
+	return max(ans1,ans2);
+}
+int main()
+{
+	int n=read_int();
+	_rep(i,1,n){
+		int u=read_int(),v=read_int(),w=read_int();
+		Insert(u,v,w,i);
+		Insert(v,u,w,i);
+	}
+	LL ans=0;
+	_rep(u,1,n){
+		if(!node_vis[u])
+		ans+=solve(u);
+	}
+	if(ans%2==0)
+	printf("%lld.0",ans/2);
+	else
+	printf("%lld.5",ans/2);
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具