P4244 [SHOI2008]仙人掌图 II（仙人掌+树形DP）
LawrenceSivan · · 题解
P4244 [SHOI2008]仙人掌图 II
前言
这是仙人掌的入门题目了。
这道题也让我学到了很多东西，所以来写一篇题解。
希望也能帮到大家qwq
题意
给定一个仙人掌，求出它的直径。
思路
看到求直径，首先可以联想到求树的直径。
对于树的直径，我们主要有两种方式：两次 DFS 或者 BFS，和树形 DP。
然后这个题直接使用 BFS 求解可以获得 70 分
具体做法是：
对于两次 BFS 或者 DFS ，首先任意地选择一个点，开始对树进行遍历，寻找最远的一个点，之后再从这个点开始，再次进行一次遍历，再次找到距离这个点最远的点。于是就求出了直径。关于证明可以从网上搜一搜，这里就不提了，今天的重点不是它
对于 DP ，可以得到以下过程：
void DP(int u){
vis[u]=1;
for(re int i=head[u];i;i=nxt[i]){
int v=to[i];
if(vis[v])continue;
DP(v);
ans=max(ans,f[u]+f[v]+val[i]);
f[u]=max(f[u],f[v]+val[i]);
}
}但是对于仙人掌上的环，我们就不能这么去操作了。
考虑如何把仙人掌上的环消去。
需要使用圆方树。
如果你还不会圆方树
关于圆方树的概念及构造方法就不再多说了，这里主要是想说一说这道题的细节。
由于在构建圆方树的过程中，会把环变成一个菊花图，二这些针对的都是圆方树上方圆边或者圆方边。
对于树上的圆圆边是不会有影响的，因为环肯定不会出在圆圆边上。
所以对于圆方树的圆圆边，其实就是普通的树边，所以我们可以直接使用树形 DP 来进行转移。
如何判断到底是不是圆圆边呢？
根据定义，发现圆圆边不在环上，所以我们只需要判断两个点是不是满足不在环上就可以了。
回忆建树的 tarjan 过程，我们根据 dfs 序的大小以及 追溯值 low 来判断访问节点顺序的先后以及他们的位置关系。
当 low[v]>dfn[u] 时，说明 v 这个节点只能回到比 u 更靠下的位置上，所以他们不会组成一个环。
于是找出了圆圆边。
直接转移即可。
if(low[v]>dfn[u]){//不在环上，大力树形DP
ans=max(ans,f[u]+f[v]+1);
f[u]=max(f[u],f[v]+1);
}对于在环上的点，我们需要单独处理。
于是我们直接把这一条链都取出来单独来看。
问题在于我们如何找到一条链，就算找到了如何把它提取出来呢？
回忆 tarjan 的过程，也就是 dfs 的过程，每次都会沿着树边向前走，且每个点只会经过一次。
对于一个环，必定会有一条边经过不到。
如图所示：
从
可以发现判断条件是
于是一旦满足了这个条件，意味着我们当前找到的节点
有了两头的节点，我们就可以顺势找出一整个环将它提取出来。
具体做法是从环的结束开始，每次跳他在搜索树中的父亲，直到调到环的起始为止。
可以用一个数组存储这个环。
有了环之后，我们需要计算环上的 dp 值了。
对于环上的两个点，如果想要计算 dp 数组的值，就需要知道两个节点在环上的距离。
注意在环上距离指的是两点较小的那个环上距离。
首先对于一个环，他的起始于结束部位相连的地方是不好处理的。
可以考虑环问题的套路处理方式：断环为链，复制一倍。
这样我们每次只计算不超过半个环长的部分，这样就可以找出较短的那一个了。
tot=0;
for(re int i=x;i!=fa[y];i=fa[i])g[++tot]=f[i];
for(re int i=1;i<=tot;i++)g[i+tot]=g[i];转移方程是
ans=max(ans,f[i]+f[j]+(i-j))
其中，
具体含义就是两个点的 dp 值之和加上两点在环上的距离。
发现这个式子只有一次项，是可以使用单调队列的。
发现这个式子其实就是求
循环的时候
所以得到维护队列单调性的条件：
g[q[tail]]-q[tail]<g[i]-i
上面的
最后不要忘记更新环的起始位置的 dp 值。
细节相关
- 对于每次提取链。
由于我们是沿着环按照 dfs 序递增的顺序访问的。
所以如果我们直接跳回环的起始位置，相当于我们的环是倒着存储的。
需不需要正过来呢？
不需要。
因为这个环本身就是任意的，你也不知道你会从哪里进来。
直接在环上 dp 就行了。
但是有一点需要注意。
如果你真的非要把他正过来，有一些细节需要注意。
观察这个图：
如果你直接跳回来，那么存环的序列就是：
一号下标是
而如果你反过来：
一号下标是
虽然
所以正过来的话需要从
关于最后根节点的 dp值更新：
同样的也要分开看，反着的直接更新：
for(re int i=1;i<=tot;i++)f[x]=max(f[x],g[i]+min(i,tot-i));
正着的需要注意，
for(re int i=2;i<=tot;i++)f[x]=max(f[x],g[i]+min(i-1,tot-i+1));
同时给出正向和反向的代码：
正向：
//#define LawrenceSivan
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define INF 0x3f3f3f3f
#define re register
const int maxn=1e5+5;
int n,m,ans;
int hd[maxn],to[maxn<<1],nxt[maxn<<1],cnt;
inline void add(int u,int v){
nxt[++cnt]=hd[u];
to[cnt]=v;
hd[u]=cnt;
}
int f[maxn],q[maxn],head,tail,g[maxn],tot;
//ans=max(ans,f[i]+f[j]+dis(i,j))
//dis(i,j)为他们在环上的较短距离
//为了保证是较短距离，断环为链，加倍处理，当长度超过半环就队头出队
int dfn[maxn],low[maxn],fa[maxn],num;
void solve(int x,int y){
tot=0;
for(re int i=y;i!=fa[x];i=fa[i])g[++tot]=f[i];
for(re int i=1;i<=tot;i++)g[i+tot]=g[i];
reverse(g+1,g+1+tot*2);
head=1,tail=0;q[++tail]=1;
for(re int i=2;i<=(tot<<1);i++){
while(head<=tail&&i-q[head]>(tot>>1))head++;
ans=max(ans,g[i]+g[q[head]]+(i-q[head]));
while(head<=tail&&g[q[tail]]-q[tail]<g[i]-i)tail--;
q[++tail]=i;
}
for(re int i=2;i<=tot;i++)f[x]=max(f[x],g[i]+min(i-1,tot-i+1));
}
void tarjan(int u){
dfn[u]=low[u]=++num;
for(re int i=hd[u];i;i=nxt[i]){
int v=to[i];
if(v==fa[u])continue;
if(!dfn[v]){
fa[v]=u;
tarjan(v);
low[u]=min(low[u],low[v]);
}
else low[u]=min(low[u],dfn[v]);
if(low[v]>dfn[u]){//不在一个环上，大力树形DP
ans=max(ans,f[u]+f[v]+1);
f[u]=max(f[u],f[v]+1);
}
}
for(re int i=hd[u];i;i=nxt[i]){
int v=to[i];
if(fa[v]==u)continue;//要找的是非树边，树边不要
if(dfn[v]>dfn[u])solve(u,v);//找到环的两个端点，把环拎出来单独算
}
}
template<typename T>
inline void read(T &x){
x=0;T f=1;char ch=getchar();
while (!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
x*=f;
}
signed main() {
#ifdef LawrenceSivan
freopen("aa.in", "r", stdin);
freopen("aa.out", "w", stdout);
#endif
read(n),read(m);
for(re int i=1,x,u,v;i<=m;i++){
read(x);read(u);x--;
while(x--){
read(v);add(u,v);add(v,u);u=v;
}
}
tarjan(1);
printf("%d\n",ans);
return 0;
}
反向
//#define LawrenceSivan
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define INF 0x3f3f3f3f
#define re register
const int maxn=1e5+5;
int n,m,ans;
int hd[maxn],to[maxn<<1],nxt[maxn<<1],cnt;
inline void add(int u,int v){
nxt[++cnt]=hd[u];
to[cnt]=v;
hd[u]=cnt;
}
int f[maxn],q[maxn],head,tail,g[maxn],tot;
//ans=max(ans,f[i]+f[j]+dis(i,j))
//dis(i,j)为他们在环上的较短距离
//为了保证是较短距离，断环为链，加倍处理，当长度超过半环就队头出队
int dfn[maxn],low[maxn],fa[maxn],num;
void solve(int x,int y){
tot=0;
for(re int i=y;i!=fa[x];i=fa[i])g[++tot]=f[i];
for(re int i=1;i<=tot;i++)g[i+tot]=g[i];
head=1,tail=0;q[++tail]=0;
for(re int i=1;i<=(tot<<1);i++){
while(head<tail&&i-q[head]>(tot>>1))head++;
ans=max(ans,g[i]+g[q[head]]+(i-q[head]));
while(head<tail&&g[q[tail]]-q[tail]<g[i]-i)tail--;
q[++tail]=i;
}
for(re int i=1;i<=tot;i++)f[x]=max(f[x],g[i]+min(i,tot-i));
}
void tarjan(int u){
dfn[u]=low[u]=++num;
for(re int i=hd[u];i;i=nxt[i]){
int v=to[i];
if(v==fa[u])continue;
if(!dfn[v]){
fa[v]=u;
tarjan(v);
low[u]=min(low[u],low[v]);
}
else low[u]=min(low[u],dfn[v]);
if(low[v]>dfn[u]){//不在一个环上，大力树形DP
ans=max(ans,f[u]+f[v]+1);
f[u]=max(f[u],f[v]+1);
}
}
for(re int i=hd[u];i;i=nxt[i]){
int v=to[i];
if(fa[v]==u)continue;//要找的是非树边，树边不要
if(dfn[v]>dfn[u])solve(u,v);//找到环的两个端点，把环拎出来单独算
}
}
template<typename T>
inline void read(T &x){
x=0;T f=1;char ch=getchar();
while (!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
x*=f;
}
signed main() {
#ifdef LawrenceSivan
freopen("aa.in", "r", stdin);
freopen("aa.out", "w", stdout);
#endif
read(n),read(m);
for(re int i=1,x,u,v;i<=m;i++){
read(x);read(u);x--;
while(x--){
read(v);add(u,v);add(v,u);u=v;
}
}
tarjan(1);
printf("%d\n",ans);
return 0;
}