文章目錄

• 前言
• 解析
• • 找環(huán)
  • • 代碼
• 練習(xí)
• 環(huán)套樹(shù)的直徑
• • 代碼
• thanks for reading！

前言

環(huán)套樹(shù)者，一個(gè)環(huán)套一棵樹(shù)也

解析

定義：n個(gè)點(diǎn)，n條邊的無(wú)向連通圖
其實(shí)就是樹(shù)多了一條邊，連出了一個(gè)環(huán)

性質(zhì)：如果對(duì)環(huán)套樹(shù)進(jìn)行dfs，多出的一條非樹(shù)邊一定是一條返祖邊

考慮dfs的過(guò)程如果它不是返祖邊，dfs的時(shí)候就會(huì)直接從這條邊過(guò)去，該邊就會(huì)成為樹(shù)邊了

找環(huán)

如何在環(huán)套樹(shù)上找到非樹(shù)邊？
考慮dfs，如果出邊指向已經(jīng)被搜過(guò)的點(diǎn)，那么這條邊（和它的反向邊）就是非樹(shù)邊
注意！：這里dfs的時(shí)候不能傳來(lái)到當(dāng)前節(jié)點(diǎn)的節(jié)點(diǎn)fa，而是要傳來(lái)到這個(gè)條的邊，否則在n=2的時(shí)候會(huì)找不到非樹(shù)邊

代碼

void find_circle(int x,int pre){vis[x]=1;for(int i=fi[x];~i;i=p[i].nxt){if(i==(pre^1)) continue;int to=p[i].to;if(vis[to]){e=i;u=x;v=to;continue;}find_circle(to,i);} }

練習(xí)

城市環(huán)路
騎士
兩道很接近的較水的題
解決環(huán)套樹(shù)后就變成沒(méi)有上司的舞會(huì)了

環(huán)套樹(shù)的直徑

找出環(huán)上的所有點(diǎn)
首先考慮不經(jīng)過(guò)環(huán)的路徑對(duì)每個(gè)點(diǎn)跑一遍樹(shù)形dp，求出每個(gè)點(diǎn)不包含環(huán)上的點(diǎn)的子樹(shù)的直徑
答案首先可以對(duì)這些直徑取ma嘗試作為答案
下面考慮經(jīng)過(guò)環(huán)的路徑
剛才dp時(shí)可以順便求出連在每個(gè)環(huán)上點(diǎn)上的最長(zhǎng)鏈len
那么經(jīng)過(guò)環(huán)的最長(zhǎng)路徑就可以表示為：
$$le{n}_i+le{n}_j+dist(i,j)$$
考慮求上面的最大值，可以破環(huán)成鏈，倍長(zhǎng)后用單調(diào)隊(duì)列優(yōu)化解決

代碼

（本題調(diào)來(lái)調(diào)去，代碼有些屎山）

#include<bits/stdc++.h> using namespace std; const int N=1e6+100; #define ll long long #define I register int ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } int n; struct node{int to,nxt,v; }p[N<<1]; int fi[N],cnt=-1; void addline(int x,int y,int v){p[++cnt]=(node){y,fi[x],v};fi[x]=cnt; } ll ans; int u,v,fa[N],fv[N]; bool vis[N]; int id[N],E=-1; void find_circle(int x,int pre){//printf("x=%d fa=%d\n",x,fa[x]);vis[x]=1;for(int i=fi[x];~i;i=p[i].nxt){if(i==(pre^1)) continue;if(i==E||i==(E^1)) continue;int to=p[i].to;if(vis[to]){E=i;u=x;v=to;continue;}fa[to]=x;fv[to]=p[i].v;find_circle(to,i);} } ll dis[N],d[N]; void dfs(int x,int f){ll mx=0,sec=0;d[x]=0;for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(to==f||id[to]){//printf(" fail:x=%d to=%d\n",x,to);continue;}dfs(to,x);ll now=dis[to]+p[i].v;//printf(" x=%d to=%d now=%lld\n",x,to,now);if(now>mx) swap(now,mx);if(now>sec) swap(now,sec);d[x]=max(d[x],d[to]);}//printf("x=%d mx=%lld sec=%lld\n",x,mx,sec);dis[x]=mx;d[x]=max(d[x],mx+sec); } int q[N],st,ed,len; ll sum[N<<1]; ll val(int x,int now){now--; // printf("val:x=%d now=%d id=%d res=%lld\n",x,now,id[x],dis[x]+max(sum[now]-sum[id[x]-1],sum[len]-(sum[now])+sum[id[x]-1]));return dis[x]+max(sum[now]-sum[id[x]-1],sum[len]-(sum[now])+sum[id[x]-1]); } ll a[N<<1],dd[N<<1]; void solve(int x){find_circle(x,-2);int uu=u;len=1;id[uu]=1;while(uu!=v){len++;uu=fa[uu];id[uu]=len;}uu=u;ll res=0;dfs(u,0);res=max(res,d[u]);while(uu!=v){uu=fa[uu];dfs(uu,0);res=max(res,d[uu]);}for(uu=u;1;uu=fa[uu]){//printf("u=%d dis=%lld d=%lld\n",uu,dis[uu],d[uu]);if(uu==v) break;}for(uu=u;uu!=v;uu=fa[uu]){a[id[uu]]=fv[uu];dd[id[uu]]=dis[uu];sum[id[uu]]=sum[id[uu]-1]+fv[uu];}a[len]=p[E].v;sum[len]=sum[len-1]+p[E].v;dd[len]=dis[v];for(int i=len+1;i<=2*len;i++){a[i]=a[i-len];dd[i]=dd[i-len];sum[i]=sum[i-1]+a[i];}//for(int i=1;i<=2*len;i++) printf("i=%d a=%lld sum=%lld dd=%lld\n",i,a[i],sum[i],dd[i]);st=1,ed=1;q[1]=1;for(int i=2;i<=2*len;i++){//printf("i=%d len=%d",i,len);while(st<=ed&&i-q[st]>=len) st++;//printf(" i=%d st=%d res=%lld+%lld+%lld-%lld\n",i,q[st],dd[q[st]],dd[i],sum[i],sum[q[st]]);res=max(res,dd[q[st]]+dd[i]+sum[i-1]-sum[q[st]-1]);while(st<=ed&&dd[q[ed]]-sum[q[ed]-1]<=dd[i]-sum[i-1]) ed--;q[++ed]=i;}ans+=res; // printf("x=%d res=%lld\n\n",x,res); } int main(){memset(fi,-1,sizeof(fi));n=read();for(int i=1;i<=n;i++){int x=read(),y=read();addline(i,x,y);addline(x,i,y);}for(int i=1;i<=n;i++){if(!vis[i]){solve(i);}}printf("%lld",ans); } /* 5 2 1 3 3 1 2 2 5 2 4 */

thanks for reading！

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的模板：环套树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。