基环树 P2607 [ZJOI2008] 骑士 没有上司的舞会的加强版，找到基环树的环之后断开一条边，以断边的两个端点为根 dp 即可，注意原图可能是森林。 代码： C++ #include using namespace std; #define int long long const int N=1e6+5; struct edge{int v,id;}; vector g[N]; int n,ans,r1,r2,E,a[N],v[N],dp[N][2]; void find(int u,int p){ v[u]=1; for(auto e:g[u]){ if(e.id==(p^1))continue; if(v[e.v]){ if(!E){r1=u,r2=e.v,E=e.id;} continue; } find(e.v,e.id); } } void dfs(int u,int p){ dp[u][0]=0,dp[u][1]=a[u]; for(auto e:g[u]){ if(e.id==p||e.id==(p^1)||e.id==E||e.id==(E^1))continue; dfs(e.v,e.id); dp[u][0]+=max(dp[e.v][0],dp[e.v][1]); dp[u][1]+=dp[e.v][0]; } } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n; for(int i=1,w,u,tot=1;i>w>>u; a[i]=w; g[i].push_back({u,++tot}); g[u].push_back({i,++tot}); } for(int i=1;i `#include using namespace std; #define int long long const int N=1e6+5; struct edge{int v,id;}; vectoredge> g[N]; int n,ans,r1,r2,E,a[N],v[N],dp[N][2]; void find(int u,int p){ v[u]=1; for(auto e:g[u]){ if(e.id==(p^1))continue; if(v[e.v]){ if(!E){r1=u,r2=e.v,E=e.id;} continue; } find(e.v,e.id); } } void dfs(int u,int p){ dp[u][0]=0,dp[u][1]=a[u]; for(auto e:g[u]){ if(e.id==p||e.id==(p^1)||e.id==E||e.id==(E^1))continue; dfs(e.v,e.id); dp[u][0]+=max(dp[e.v][0],dp[e.v][1]); dp[u][1]+=dp[e.v][0]; } } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n; for(int i=1,w,u,tot=1;in;i++){ cin>>w>>u; a[i]=w; g[i].push_back({u,++tot}); g[u].push_back({i,++tot}); } for(int i=1;in;i++) if(!v[i]){ E=0; find(i,-1); dfs(r1,0);int t=dp[r1][0]; dfs(r2,0);ans+=max(t,dp[r2][0]); } coutans; return 0; }` P5022 [NOIP 2018 提高组] 旅行 + P5049 [NOIP 2018 提高组] 旅行 加强版 直接按照加强版的数据来做。 对于 m=n-1 的情况，直接将子节点排序再 DFS 即可。 对于 m=n，也就是基环树的情况，我们考虑先找出环。当从根节点出发，走到环上。当我们在环上使用回溯时，就相当于断开了当前点到回溯点的那条边、之后就可以按照树的方法来做。考虑贪心在什么情况下回溯：当环上下一个点比回溯后能访问的点要大时，选择回溯。 代码： C++ #include using namespace std; const int N=5e5+5; int n,m,tag,h[N],vis[N],f[N]; vector t[N]; void dfs(int u,int fa){ cout(nxt?nxt:b)){ tag=1; continue; } } dfs2(v,nxt?nxt:b); } } int main(){ ios::sync_with_stdio(0);cin.tie(0); cin>>n>>m; for(int i=1,u,v;i>u>>v; t[u].push_back(v); t[v].push_back(u); } for(int i=1;i `#include using namespace std; const int N=5e5+5; int n,m,tag,h[N],vis[N],f[N]; vectorint> t[N]; void dfs(int u,int fa){ coutu" "; for(int v:t[u]) if(v!=fa) dfs(v,u); } void dfs1(int u,int fa){ vis[u]=1,f[u]=fa; for(int v:t[u]){ if(v==fa) continue; if(vis[v]){ if(!tag){ tag=1,h[v]=1; int x=u; while(x!=v) h[x]=1,x=f[x]; } } else dfs1(v,u); } } void dfs2(int u,int b){ vis[u]=1; coutu" "; for(int i=0;it[u].size();i++){ int v=t[u][i]; if(vis[v]) continue; int nxt=0; for(int j=i+1;j(int)t[u].size();j++) if(!vis[t[u][j]]){ nxt=t[u][j]; break; } if(h[u]&&h[v]&&!tag){ if(v>(nxt?nxt:b)){ tag=1; continue; } } dfs2(v,nxt?nxt:b); } } int main(){ ios::sync_with_stdio(0);cin.tie(0); cin>>n>>m; for(int i=1,u,v;im;i++){ cin>>u>>v; t[u].push_back(v); t[v].push_back(u); } for(int i=1;in;i++) sort(t[i].begin(),t[i].end()); if(m==n-1){ dfs(1,-1); return 0; } dfs1(1,-1); tag=0; memset(vis,0,sizeof vis); dfs2(1,1e9); return 0; }` P4381 [IOI 2008] Island 观察样例，启发我们答案应该是每颗基环树的直径之和，问题转化为怎么求基环树的直径。 基环树的直径应该有两种可能，一种是以环上一点为根的子树的直径、一种是环上取两点的子树深度之和加上两点之间的距离，注意以上提到的子树的每个节点都不在环上。 对于第一种直接套模板就行。对于第二种情况，设环上一点 u 子树深度为 d_u，环的前缀和数组为 dis，就相当于求 $d_i+d_j+dis_i-dis_j(1\le j代码： C++ #include using namespace std; #define int long long const int N=1e6+5; int n,mx,rt,idx,ans,sum; int vis[N],h[N],dp[N],dis[N r; struct node{ int v,w,id; }f[N]; vector t[N]; void dfs1(int u,int fa){ vis[u]=1; for(node x:t[u]){ int v=x.v,w=x.w; if(x.id==fa) continue; if(!vis[v]){ f[v]={u,w,x.id}; dfs1(v,x.id); } else if(!idx){ vector a; int p=u; while(p!=v) a.push_back(p),p=f[p].v; a.push_back(v); reverse(a.begin(),a.end()); idx=a.size(); for(int i=0;i>n; for(int i=1;i>v>>w; t[i].push_back({v,w,i}); t[v].push_back({i,w,i}); } for(int i=1;i q; for(int i=1;iidx) q.pop_front(); if(q.size()) sum=max(sum,q.front().v+l[i]+dis[i]); while(q.size()&&q.back().v `#include using namespace std; #define int long long const int N=1e6+5; int n,mx,rt,idx,ans,sum; int vis[N],h[N],dp[N],dis[N1],d[N],l[N1]; vectorint> r; struct node{ int v,w,id; }f[N]; vectornode> t[N]; void dfs1(int u,int fa){ vis[u]=1; for(node x:t[u]){ int v=x.v,w=x.w; if(x.id==fa) continue; if(!vis[v]){ f[v]={u,w,x.id}; dfs1(v,x.id); } else if(!idx){ vectorint> a; int p=u; while(p!=v) a.push_back(p),p=f[p].v; a.push_back(v); reverse(a.begin(),a.end()); idx=a.size(); for(int i=0;iidx;i++) r.push_back(a[i]),h[a[i]]=1; for(int i=2;iidx;i++) dis[i]=dis[i-1]+f[a[i-1]].w; int s=dis[idx]+w; for(int i=idx+1;i(idx1);i++) dis[i]=dis[i-idx]+s; } } } void dfs2(int u,int fa){ dp[u]=0; for(node x:t[u]){ int v=x.v,w=x.w; if(v==fa||h[v]) continue; dfs2(v,u); mx=max(mx,dp[u]+dp[v]+w); dp[u]=max(dp[u],dp[v]+w); } } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n; for(int i=1;in;i++){ int v,w; cin>>v>>w; t[i].push_back({v,w,i}); t[v].push_back({i,w,i}); } for(int i=1;in;i++) if(!vis[i]){ r.clear(); idx=0,sum=0; dfs1(i,-1); for(int i=0;i(int)r.size();i++){ int x=r[i]; mx=0; dfs2(x,-1); l[i+1]=l[i+idx+1]=dp[x]; sum=max(sum,mx); } dequenode> q; for(int i=1;i(idx1);i++){ while(q.size()&&i-q.front().w+1>idx) q.pop_front(); if(q.size()) sum=max(sum,q.front().v+l[i]+dis[i]); while(q.size()&&q.back().vl[i]-dis[i]) q.pop_back(); q.push_back({l[i]-dis[i],i,0}); } ans+=sum; } coutans; return 0; } `
基环树
笔记