参考TiAmoZhang 的帖子参考I_LOVE_MATH 的文章概念一个环上面挂了很多子树有n个节点和n条边的图如果不保证连通的话那么整张图是一张基环树森林并且如果将环上的任意一条边去除那么整棵基环树会成为一棵普通的树。第一步找环有向直接DFS回到根就是一个环无向可以使用并查集不会有重边所以有集内的边就形成了环之后可以把环上任意一条边去除变树转化为树上问题典:P2607 [ZJOI2008] 骑士代码建有向图 DFS找环constintN1e610,M1e5;constdoublePIacos(-1),eps1e-12;constlonglongmod998244353,inf1e1810,up1e9;inta[N],vis[N];vectorintg[N];// 有向边/* 直观来想 答案和树的深度有关 找环 以环上两点分别作为根 去掉环上一条边形成树 会有两种答案(奇/偶深度) 环上其他边去掉也一样 树形dp找最大的答案 */intr1,r2;voiddfs(intnow,intrt){// dfs找环vis[now]1;for(autox:g[now]){if(xrt){r1x,r2now;return;}if(vis[x])continue;dfs(x,rt);}}intdp[N][2];intdfs2(intnow,intrt){// 树形dp// vis2[now]1;dp[now][1]a[now];dp[now][0]0;for(autox:g[now]){if(xrt)continue;// 因为一个联通集要跑两边 不用vis记号了 直接看根来判环dfs2(x,rt);// 算总子树和dp[now][0]max(dp[x][0],dp[x][1]);// 本次不选 子树可选可不选dp[now][1]dp[x][0];// 本次选 孩子不选}returndp[now][0];// 直接用函数执行后的返回值 因为每次dfs2都会改变dp}voidsolve(){intn;cinn;forr(i,1,n){inthate;cina[i]hate;g[hate].push_back(i);}intsm0;forr(i,1,n){if(vis[i])continue;/* //一定会找到环的吧 dfs(i,i); coutr1 r2endl; smmax(dfs2(r1,r1),dfs2(r2,r2));//r1 r2不能同时选 不一定 可能这个点在环外 但是和环联通 在之前找环的时候可能遍历不到 从这个点出发也找不到之前找完的环 如 2 1 2 2的3、4点 */r1r20;dfs(i,i);// coutr1 r2endl;if(r1){dfs2(r1,r1);smmax(dfs2(r1,r1),dfs2(r2,r2));//r1 r2不能同时选 返回的是dp[rt][0]}}coutsmendl;}2025ZJCPC L. Nailoongs Always Lie有自环但是对答案无贡献建有向图找环方法用了并查集答案找法类似上面典题。constintN1e510,M1e5;constdoublePIacos(-1);constlonglongmod998244353,inf2e18;vectorintg[N];// 并查集找环intfa[N],vis[N],cnt[N][2];// cnt[][1奶龙/0不是]intfindf(intx){returnfa[x](fa[x]x?x:findf(fa[x]));}intdfs(intnow,intf){// 树形dp找答案vis[now]1;cnt[now][0]0;cnt[now][1]1;for(autox:g[now]){if(xf||vis[x])continue;dfs(x,now);cnt[now][0]max(cnt[x][0],cnt[x][1]);cnt[now][1]cnt[x][0];}vis[now]0;// 回复现场returncnt[now][0];}voidsolve(){/* 自环 自己说自己是奶龙 必然是说假话的其他生物 */intn;cinn;forr(i,1,n)fa[i]i;vectorinta(n1);vectorpiicir;forr(i,1,n){cina[i];g[a[i]].push_back(i);intfxfindf(a[i]),fyfindf(i);if(fx!fy)fa[fy]fx;elsecir.push_back({a[i],i});}intans0;for(auto[u,v]:cir){ansmax(dfs(u,0),dfs(v,0));}coutansendl;}