欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[bzoj1023][SHOI2008]cactus仙人掌图【仙人掌】

程序员文章站 2022-05-22 09:57:20
...

【题目链接】
  http://www.lydsy.com/JudgeOnline/problem.php?id=1023
【题解】
  仙人掌入门题,拿圆方树练练手。
  圆方树就是把一个环建一个新方点,然后向每个在环上的点连边,
  接下来就很方便了,用dp的方式求出直径(以这个点为子树的最大直径),在遇到方点时,在环上转两圈。
  复杂度 O(m+nm+n)
  tips:vector用起来很爽

/* --------------
    user Vanisher
    problem bzoj-1023 
----------------*/
# include <bits/stdc++.h>
# define    N       500010
using namespace std;
struct node{
    int data,vote;
};
vector <node> e[N];
int use[N],low[N],dfn[N],ti,st[N],top,num,f[N],ans,h[N],po[N],n,m,su[N],sv[N],len,tag[N],place,fx;
int read(){
    int tmp=0, fh=1; char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') fh=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){tmp=tmp*10+ch-'0'; ch=getchar(); }
    return tmp*fh;
}
void build(int u, int v, int w){
    e[u].push_back((node){v,w});
    e[v].push_back((node){u,w});
}
void tarjan(int x, int fa){
    use[x]=true; low[x]=dfn[x]=++ti; 
    for (int ed=1; ed<e[x].size(); ed++){
        if (dfn[x]<dfn[e[x][ed].data]||e[x][ed].data==fa) continue;
        st[++top]=x;
        if (use[e[x][ed].data]==false) {
            tarjan(e[x][ed].data,x);
            if (st[top]==x){
                su[++place]=x, sv[place]=e[x][ed].data;
                top--;
            }
        }
        else {
            int to=e[x][ed].data;
            e[++num].push_back((node){0,0});
            int s=top;
            while (st[top]!=to) top--;
            for (int i=top; i<=s; i++) 
                e[num].push_back((node){st[i],min(s-i+1,i-top)});
            tag[num]=s-top+1; top--;
        }
    }
}
void dp(int x, int fa){
    if (tag[x]==0){
        int mx1=0, mx2=0;
        for (int ed=1; ed<e[x].size(); ed++)
            if (e[x][ed].data!=fa){
                dp(e[x][ed].data,x);
                int now=f[e[x][ed].data]+e[x][ed].vote;
                if (now>mx1) mx2=mx1, mx1=now;
                    else if (now>mx2) mx2=now;
            }
        ans=max(ans,mx1+mx2);
        f[x]=mx1;
    }
    else {
        for (int ed=1; ed<e[x].size(); ed++)
            if (e[x][ed].data!=fa){
                int t=e[x][ed].data;
                dp(e[x][ed].data,x);
                f[x]=max(f[e[x][ed].data]+e[x][ed].vote,f[x]); 
            }
        for (int ed=1; ed<e[x].size(); ed++)
            if (e[x][ed].data!=fa) h[ed]=f[e[x][ed].data];
            else h[ed]=0;
        int pl=1, pr=0;
        for (int i=1; i<e[x].size(); i++){
            while (pl<=pr&&i-po[pl]>tag[x]/2) pl++;
            if (pl<=pr) ans=max(ans,h[i]+st[pl]+i-po[pl]);
            while (pl<=pr&&h[i]-i>=st[pr]-po[pr]) pr--;
            st[++pr]=h[i], po[pr]=i;
        }
        for (int i=1; i<e[x].size(); i++){
            while (pl<=pr&&i+tag[x]-po[pl]>tag[x]/2) pl++;
            if (pl<=pr) ans=max(ans,h[i]+st[pl]+i+tag[x]-po[pl]);
            while (pl<=pr&&h[i]-i-tag[x]>=st[pr]-po[pr]) pr--;
            st[++pr]=h[i], po[pr]=i+tag[x];
        }
    }
}
int main(){
    n=read(), m=read(); num=n; int sum=0;
    for (int i=1; i<=n; i++) e[i].push_back((node){0,0});
    for (int i=1; i<=m; i++){
        int l=read(),la=read();
        for (int j=2; j<=l; j++){
            int now=read();
            build(la,now,1);
            la=now;
        }
    }
    tarjan(1,0);
    for (int i=1; i<=n; i++) e[i].clear(), e[i].push_back((node){0,0});
    for (int i=n+1; i<=num; i++)
        for (int j=1; j<e[i].size(); j++) 
            e[e[i][j].data].push_back((node){i,e[i][j].vote});
    for (int i=1; i<=place; i++)
        build(su[i],sv[i],1);
    dp(1,0);
    printf("%d\n",ans);
    return 0;
}