P6335 [COCI 2007/2008 #1] STAZA题解

zpy12345 · 2026-04-21 17:28:47 · 题解

安利一下我的博客。

继续水题解！

题意

求从点 1 出发的最长路径的边的数量，可以经过重复点但不能经过重复边，图为仙人掌图。

思路

看到仙人掌图，可以考虑建出圆方树试一下。建出圆方树后，由于要求最长路径，可以尝试 DP，我们需要在每个圆点维护两个值，dp_x 表示从 x 出发，在 x 的子树内走最后回到 x 的最长路径的边的数量，dpp_x 表示从 x 出发，在 x 的子树内走最后不要求一定回到 x 的最长路径的边的数量。

• 对于 dp_x，其值为 x 所在环上所有点的 dp 之和加上环长。
• 对于 dpp_x，我们需要在 x 所在环上找一个点 u，取其 dpp_u，再找一条 x\to u 的环上路径，这条路径上的点都取其 dp。正着扫一遍反着扫一遍即可。

说起来还是太费劲了，不过应该不难理解。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
vector<int> b[N],a[N];
int dfn[N],low[N],num=0,cnt=0;
stack<int> q;
void dfs(int x)
{
    q.push(x),dfn[x]=low[x]=++num;
    for(int i=0;i<b[x].size();i++)
        if(!dfn[b[x][i]])
        {
            dfs(b[x][i]);
            low[x]=min(low[x],low[b[x][i]]);
            if(low[b[x][i]]==dfn[x])
            {
                cnt++,a[cnt].push_back(x),a[x].push_back(cnt);
                while(!q.empty())
                {
                    int t=q.top();
                    q.pop();
                    a[cnt].push_back(t),a[t].push_back(cnt);
                    if(t==b[x][i]) break;
                }
            }
        }
        else low[x]=min(low[x],dfn[b[x][i]]);
}
int dp[N],dpp[N];
void dfss(int x,int fa)
{
    if(x>n)
    {
        for(int i=0;i<a[x].size();i++)
            if(a[x][i]!=fa) dfss(a[x][i],x);
        return ;
    }
    int min1=-1e9;
    for(int i=0;i<a[x].size();i++)
        if(a[x][i]!=fa)
        {
            int to=a[x][i],yu=1,now=0;
            dfss(a[x][i],x);
            dp[x]++;
            vector<int> p;
            for(int j=0;j<a[to].size();j++)
                if(a[to][j]!=x) dp[x]+=dp[a[to][j]]+1,yu+=dp[a[to][j]]+1;
                else now=j;
            if(a[to].size()==2) dp[x]-=yu,yu=0; //注意特判一条边的情况
            for(int j=now+1;j<a[to].size();j++) p.push_back(a[to][j]);
            for(int j=0;j<now;j++) p.push_back(a[to][j]);
            int max1=0,sum=1;
            for(int i=0;i<p.size();i++) max1=max(max1,sum+dpp[p[i]]),sum+=dp[p[i]]+1;
            sum=1;
            for(int i=p.size()-1;i>=0;i--) max1=max(max1,sum+dpp[p[i]]),sum+=dp[p[i]]+1;
            min1=max(min1,max1-yu);
        }
    dpp[x]=dp[x]+min1,dpp[x]=max(dpp[x],dp[x]);
}
int main()
{ 
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    cnt=n;
    while(m--)
    {
        int u,v;
        cin>>u>>v;
        b[u].push_back(v),b[v].push_back(u);
    }
    dfs(1),dfss(1,0);
    cout<<max(dp[1],dpp[1])<<"\n";
    return 0;
}