小红的基环树删边【牛客tracker 每日一题】

小红的基环树删边时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述小红拿到了一棵基环树她想知道若删除第i ii条边1 11号n nn号点的最短路是多少所谓基环树指n nn个点、n nn条边组成的、不包含重边和自环的无向连通图。输入描述第一行输入一个正整数n nn代表基环树的点数。接下来的n nn行每行输入两个正整数u , v u,vu,v代表节点u uu和节点v vv有一条边连接。3 ≤ n ≤ 10 5 3≤n≤10^53≤n≤1051 ≤ u , v ≤ n 1≤u,v≤n1≤u,v≤n保证给定的图为基环树。输出描述输出n nn行第i ii行输出删除第i ii条边的答案。如果删除后1 11号点和n nn号点不连通请输出− 1 -1−1否则输出一个正整数代表删除后1 11号点和n nn号点的最短路长度。示例1输入3 1 2 2 3 1 3输出1 1 2示例2输入4 1 2 2 3 2 4 3 4输出-1 2 3 2解题思路本题是基环树上删边最短路问题。基环树有n nn个点、n nn条边任意两点间的简单路径数量极少至多两条。利用这一性质可以通过 DFS 找出所有从1 11到n nn的简单路径并用路径长度更新不在此路径上的边的答案。1. 问题等价转化基环树的结构图由一个环和若干棵挂在环上的树组成。对于任意两点1 11和n nn它们之间的所有简单路径都必然经过环上的某一段可能为空且由于树部分无环路径条数最多为2 22分别沿环的两侧。删边影响删除某条边i ii后若1 11和n nn仍连通则它们的最短路一定对应原图中某条不经过边i ii的简单路径。因此对于原图中每一条从1 11到n nn的简单路径P PP路径长度l e n ( P ) len(P)len(P)可以用于更新所有不在P PP上的边的答案即ans[id] min(ans[id], len(P))。不连通判定如果某条边在所有1 → n 1\to n1→n的简单路径上都出现即该边是“必经边”那么删去后1 11和n nn将不连通答案记为− 1 -1−1。2. 算法实现DFS 枚举所有简单路径建图用邻接表存储无向边每条边记录其编号i d idid1 ∼ n 1 \sim n1∼n。初始化答案数组dp[id]初始化为一个极大值如10 9 10^9109表示删去边i d idid后的最短路径长度。DFS 搜索从节点1 11出发维护当前路径长度dep和一个标记数组vi[id]表示边i d idid是否已用在当前路径中避免重复走同一条边。遍历邻边若该边未被使用则标记、递归、回溯。当到达节点n nn时遍历所有边编号i d idid若!vi[id]则用当前路径长度dep更新dp[id]取较小值。输出结果遍历i 1 ∼ n i 1 \sim ni1∼n若dp[i]仍为极大值输出− 1 -1−1否则输出dp[i]。3. 复杂度分析时间复杂度由于基环树上1 → n 1\to n1→n的简单路径至多2 22条DFS 实际访问的节点和边规模为O ( n ) O(n)O(n)。每次到达n nn时更新所有n nn条边的答案看起来是O ( n 2 ) O(n^2)O(n2)但只会执行常数次至多2 22次总复杂度O ( n ) O(n)O(n)。空间复杂度邻接表与标记数组O ( n ) O(n)O(n)。总结利用基环树简单路径数量极少的特性直接 DFS 找出所有1 → n 1\to n1→n的不重复边路径。每条路径的长度可用来更新所有不在该路径上的边的答案最终未更新的边即为必经边删去后不连通。方法简洁且运行高效。代码简要说明全局数组g[N]邻接表存储(邻接点, 边编号)。vi[N]标记边是否在当前 DFS 路径中。dp[N]dp[i]表示删除第i ii条边后1 → n 1\to n1→n的最短路初始为10 9 10^9109。DFS 函数dfs(x, dep)若x n x nxn则遍历1 ∼ n 1\sim n1∼n的所有边如果边i ii未被标记则dp[i] min(dp[i], dep)。否则枚举邻边若边未标记则标记并递归回溯时取消标记。主函数读入n nn和n nn条边建图。调用dfs(1, 0)。输出dp[1..n]若值大于10 6 10^6106则输出− 1 -1−1否则输出该值。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N100050;constll INF1e18;constll M1e610;constll mod1e97;ll n,i,j,k,m,t;ll vi[N],dp[N];vectorpllg[N];voiddfs(ll x,ll dep){if(xn){for(i1;in;i)if(!vi[i])dp[i]min(dp[i],dep);return;}for(auto[y,id]:g[x])if(!vi[id]){vi[id]1;dfs(y,dep1);vi[id]0;}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinn;for(i1;in;i){cinjk;dp[i]1000000000LL;g[j].push_back({k,i});g[k].push_back({j,i});}dfs(1,0);for(i1;in;i){cout(dp[i]1000000?-1:dp[i])\n;}return0;}