bzoj1023 [SHOI2008]cactus 선인장 그림 트리 DP+ 단조로운 대기열

제목: 선인장 한 개에게 직경을 구하다.경전의 좋은 문제.처음엔 나비가 축소한다고 생각하고 직접 구하고, 생각해보니까 바보인 것 같아.블록 내의 것은 근본적으로 통계할 수 없다.대략적으로 DP의 해답을 생각할 수 있지만 단조로운 대기열은 진심으로 놀랐다===f[x]를 설정하면 x를 기점(위에서 아래로)의 가장 긴 경로를 나타낸다. 나무변/비나무변에 대해 각각 이동한다. 나무변은 직접 이동해야 한다. 주로 비나무변이고 비나무변은 바로 위쪽이다. 나는 고리 위의 점으로만 f[x](x는 고리 위의 깊이가 가장 작은 점)을 업데이트한다. 이것은DP가 필요하다.나무변의 경우 f[x]에 대해 f[x]=max(f[v]+1)가 있고 v∈son은 나무변이 아닌 상황: x가 고리의 깊이가 가장 작은 점으로 알려져 있기 때문에 이 고리의 나머지 점은 x와 연결되기만 하면 x로 옮길 수 있다.즉 f[x]=max(f[v]+dis(x, v)), x와 v가 한 링 안에 있으니 이 식은 이해하기 어렵지 않다.문제는 우리가 고리 안쪽을 폭력적으로 매거할 수 없다는 것이다. 디스(i, j)를 주목하면 min(j-i, n-i+j)로 표시할 수 있다. min을 없애기 위해 우리는 고리를 한 번 복제하고 매번 반 개의 고리 길이의 dp만 고려한 다음에 식자를 max(f[i]+f[j]+j-i)로 변환할 수 있다. 그러면 현재 단조로운 대기열 처리 max(f[j]+j)는 간단하다.정말 신제다.

#include
#include
#include
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=1e5+5;
const int M=5e6+5;
int n,m;
int a[N],head[N],next[M],go[M];
int low[N],dfn[N],vis[N],sta[N],tot,cnt;
int fa[N],dep[N],f[N],q[N],ans;
int read()
{
    int x=0;char ch=getchar();
    while (ch<'0'||ch>'9')ch=getchar();
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
inline void add(int x,int y)
{
    go[++tot]=y;
    next[tot]=head[x];
    head[x]=tot;
}
inline void dp(int x,int y)
{
    int tot=dep[y]-dep[x]+1;
    int t=1,w=1;
    for(int i=y;i!=x;i=fa[i])a[tot--]=f[i];
    a[1]=f[x];tot=dep[y]-dep[x]+1;
    q[1]=1;
    fo(i,1,tot)a[i+tot]=a[i];
    fo(i,2,2*tot)
    {
        if (i-q[t]>tot/2)t++;
        ans=max(ans,a[i]+i+a[q[t]]-q[t]);
        while (t<=w&&a[i]-i>=a[q[w]]-q[w])w--;
        q[++w]=i;
    }
    fo(i,2,tot)f[x]=max(f[x],a[i]+min(i-1,tot-i+1));
}
inline void dfs(int x)
{
    dfn[x]=low[x]=++cnt;
    for(int i=head[x];i;i=next[i])
    {
        int v=go[i];
        if (v==fa[x])continue;
        if (!dfn[v])
        {
            fa[v]=x;
            dep[v]=dep[x]+1;
            dfs(v);
        }
        low[x]=min(low[x],low[v]);
        if (low[v]>dfn[x])
        ans=max(ans,f[v]+f[x]+1),f[x]=max(f[x],f[v]+1);
    }
    for(int i=head[x];i;i=next[i])
    {
        int v=go[i];
        if (dfn[v]>dfn[x]&&fa[v]!=x)dp(x,v);
    }
}
int main()
{
    n=read(),m=read();
    fo(i,1,m)
    {
        int s=read(),last=0,x;
        fo(j,1,s)
        {
            x=read();
            if (last)add(last,x),add(x,last);
            last=x;
        }
    }
    dfs(1);
    printf("%d
",ans);

}