AI Summary
基环树由n个点n条边构成，有唯一环。通过三道例题讲解其常见处理方法：断环、Tarjan找环、子树直径与单调队列。
孩子们我回来更新了w
基环树
一些基础知识
基环树，可以看做由 个点和 条边构成的图，也可以看做一颗树加上一条边构成的图
所以其有一个明显的性质，存在且仅有一个环
这个环赋予了它一些特殊的处理方法 具体来看题目
P2607 [ZJOI2008] 骑士
这是一道经典的基环树例题，而且容易让人想到P1352 没有上司的舞会。这两道题本质相同，只是这道题需要有一点点处理逻辑的改变。
首先我们可以通过输入方式引出一个结论，如果我们从 讨厌的骑士 向 建边，每个点入度一定为 。
由此结论我们可以证明，基环树上的环一定是一个由有向边收尾相连的环，我们就可以通过简单的 dfs 来找到这个环。
找到环之后，考虑找到相邻的两个点，分别进行树形 dp，容易证明，答案存在于这两次 dp 的最优解中。
/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=1e6+10;
vector <int> g[N];
int n,s1,s2,res,w[N],vis[N],dp[N][2];
void dfs (int u,int rt) {
vis[u]=1;
for (int v:g[u]) {
if (v==rt) {
s1=u;
s2=v;
return;
}
if (!vis[v]) dfs(v,rt);
}
}
int dodp (int u,int rt) {
dp[u][0]=0;
dp[u][1]=w[u];
for (int v:g[u]) {
if (v==rt) continue;
dodp(v,rt);
dp[u][0]+=max(dp[v][0],dp[v][1]);
dp[u][1]+=dp[v][0];
}
return dp[u][0];
}
signed main() {
Cios;
cin>>n;
for (int i=1;i<=n;i++) {
int v;
cin>>w[i]>>v;
g[v].push_back(i);
}
for (int i=1;i<=n;i++) {
if (!vis[i]) {
s1=s2=0;
dfs(i,i);
if (s1) res+=max(dodp(s1,s1),dodp(s2,s2));
}
}
cout<<res<<"\n";
return 0;
}P5022 [NOIP 2018 提高组] 旅行 & P5049 [NOIP 2018 提高组] 旅行 加强版
我们直接考虑加强版做法。对于 时的做法不做讨论
和上一题不同，这道题我们要建双向边。因此，我们使用 Tarjan 算法求环。
求到环之后，可以发现，我们必须断开，且仅能断开一条边。
为了保证最优，我们可以在 dfs 是维护 fallback ，用于记录这个点可以回退到的第一个点编号。
当 fallback 比目前这个点能到达的最小的点还要大时，我们考虑回退，删除这条边。
/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define intl long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=5e5+10,inf=0x3f3f3f3f;
int n,m,dfn[N],low[N],dfncnt=0;
int stk[N],top=0;
bool ins[N],onc[N];
bool visd[N],deld=0;
vector<int> g[N],res;
void tarjan(int u,int fa) {
dfn[u]=low[u]=++dfncnt;
stk[++top]=u;
ins[u]=1;
for (int v:g[u]) {
if (v==fa) continue;
if (!dfn[v]) {
tarjan(v,u);
low[u]=min(low[u],low[v]);
}
else if (ins[v]) low[u] = min(low[u], dfn[v]);
}
if (low[u]==dfn[u]) {
if (stk[top]!=u) {
while (top>0) {
int x=stk[top--];
ins[x]=0;
onc[x]=1;
if (x==u) break;
}
}
else ins[u]=0,top--;
}
}
void dfs(int u,int fa,int fbk) {
int j=0;
for (int i=0;i<g[u].size();i++) {
int v=g[u][i];
if (v==fa||visd[v]) continue;
j=max(j,i+1);
while (j<g[u].size()&&(g[u][j]==fa||visd[g[u][j]])) j++;
int nxt=(j<g[u].size())?g[u][j]:fbk;
if (!deld&&onc[u]&&onc[v]&&nxt==fbk&&v>fbk) {
deld=1;
continue;
}
visd[v]=1;
res.push_back(v);
dfs(v,u,nxt);
}
}
signed main() {
Cios;
cin>>n>>m;
for (int i=1;i<=m;i++) {
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i=1;i<=n;i++) sort(g[i].begin(),g[i].end());
if (m==n) tarjan(1,0);
visd[1]=1;
res.push_back(1);
dfs(1,0,inf);
for (int i=0;i<n;i++) cout<<res[i]<<(i==n-1?"":" ");
cout<<"\n";
return 0;
}P4381 [IOI 2008] Island
我们容易联想到树的直径，但是直接套用的话难免会一直在环上打转。
我们考虑分类讨论，容易发现基环树直径存在两种情况：经过环，或者只存在于一颗挂在环上的子树上。
我们对于每个环上子树求出此子树的直径与最大深度。先将答案更新为所有子树中的直径中的最大值。
然后考虑拆环成链，并对链上的点处理前缀和 sum
之后得到式子，点 和点 间的最长距离为 ，其中 d 表示这个点在环外子树的最大深度。
整理得到 ，于是考虑将 进行单调队列处理。
/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define intl long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=1e6+10;
int n,deg[N],outto[N],outw[N];
intl dp[N],mxd[N],res=0;
struct edge {
int to,w;
};
int a[N*2];
intl sum[N*2];
vector <edge> g[N];
queue <int> q;
signed main() {
Cios;
cin>>n;
for (int i=1;i<=n;i++) {
int u,l;
cin>>u>>l;
g[u].push_back({i,l});
g[i].push_back({u,l});
deg[u]++;
deg[i]++;
outto[i]=u;
outw[i]=l;
}
for (int i=1;i<=n;i++) {
if (deg[i]==1) q.push(i);
}
while (q.size()) {
int u=q.front();
q.pop();
for (auto [v,w]:g[u]) {
if (deg[v]>1) {
mxd[v]=max({mxd[u],mxd[v],dp[v]+dp[u]+w});
dp[v]=max(dp[v],dp[u]+w);
if (--deg[v]==1) q.push(v);
}
}
}
for (int i=1;i<=n;i++) {
if (deg[i]<=1) continue;
vector <int> cir;
int cur=i;
while (deg[cur]>1) {
cir.push_back(cur);
deg[cur]=0;
cur=outto[cur];
}
int m=cir.size();
intl mxont=0,mxnot=0;
for (int j=0;j<m;j++) {
a[j+1]=a[j+1+m]=cir[j];
mxnot=max(mxnot,mxd[cir[j]]);
}
sum[1]=0;
for (int j=1;j<=2*m;j++) sum[j]=sum[j-1]+outw[a[j-1]];
deque<int> dq;
for (int j=1;j<=2*m;j++) {
while (dq.size()&&j-dq.front()>=m) dq.pop_front();
if (dq.size()) mxont=max(mxont,dp[a[j]]+dp[a[dq.front()]]+sum[j]-sum[dq.front()]);
while (dq.size()&&dp[a[j]]-sum[j]>=dp[a[dq.back()]]-sum[dq.back()]) dq.pop_back();
dq.push_back(j);
}
res+=max(mxont,mxnot);
}
cout<<res<<"\n";
return 0;
}
评论（0）
暂无评论