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

【题目链接】
　　http://www.lydsy.com/JudgeOnline/problem.php?id=1023
【题解】
　　仙人掌入门题，拿圆方树练练手。
　　圆方树就是把一个环建一个新方点，然后向每个在环上的点连边，
　　接下来就很方便了，用dp的方式求出直径（以这个点为子树的最大直径），在遇到方点时，在环上转两圈。
　　复杂度 O(m+n$m+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
",ans);
    return 0;
}