[NEERC2007][SHOI2008]Cactus Reloaded

题目大意：
　　给你一个仙人掌，求图中相距最远的点对之间的距离。

思路：
　　Tarjan+DP。
　　我们先考虑一个树的情况。
　　设用far[u]表示点u出发到其子树中叶子节点的最大距离，若v为u的子结点，很显然far[u]=max{far[v]}+1。
　　而对于经过点u的简单路径，最长的一条肯定是max{far[v]+far[w]+2}，且u≠w。
　　很显然我们只需要DFS一遍，然后随便转移即可。
　　考虑一下仙人掌和树有什么不同。
　　很显然仙人掌就是在一棵树上加了几条边，使得图中出现了一些环，而且不会有边同时出现在两个环中。
　　我们不妨先把原图的环去掉某一个边，使得剩下的图是一棵树，很容易处理出树上的情况。
　　处理到当前环中最后一条边时，再单独对这个环进行DP。
　　考虑这个环上的每一棵外向树，设u和v是这个环上的两个结点，那么far[u]+far[v]+dis(u,v)就是一个可能的答案。
　　如何让这个答案最大化？
　　对于每一个点u，我们可以枚举每一个v来得到一个可能的答案，而要让答案尽可能大，似乎可以用单调队列来转移。
　　但唯一的问题是，现在u和v是再一个环上，他们的距离是不会单调递增的，也就是说你按顺序枚举每一个点，可能先越来越远再越来越近。
　　对于这种情况，我们把环复制一遍来转移，维护队列的时候要判断一下当前待更新的点u和用来更新的点v距离是不是超过环长的一半。
　　最后再更新一下环上高度最高的点对应的far值。
　　设环的大小为size，最高点为top，那么far[top]=max(far[top],max{far[v]+dis(top,v)})。
　　这时候要注意一下，前面DFS(Tarjan)里面，far的转移要判断一下，low[v]是不是大于等于dfn[u]，如果不是，说明现在是在环上。
　　所以不能直接更新，不然后面环上DP可能会重复。

#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
inline int getint() {
    register char ch;
    while(!isdigit(ch=getchar()));
    register int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
const int N=50001;
std::vector<int> e[N];
int far[N],par[N],ans;
inline void add_edge(const int &u,const int &v) {
    e[u].push_back(v);
    e[v].push_back(u);
}
inline void dp(const int &top,const int &end,const int &size) {
    static int cir[N*2];
    static std::deque<int> q;
    for(register int i=size,v=end;i;i--) {
        cir[size+i]=cir[i]=far[v];
        v=par[v];
    }
    q.push_back(1);
    for(register int i=2;i<=size*2;i++) {
        if(i-q.front()>size/2) q.pop_front();
        ans=std::max(ans,cir[i]+cir[q.front()]+i-q.front());
        while(!q.empty()&&cir[q.back()]-q.back()<=cir[i]-i) q.pop_back();
        q.push_back(i);
    }
    q.clear();
    for(register int i=2;i<=size;i++) {
        far[top]=std::max(far[top],cir[i]+std::min(i-1,size-i+1));
    }
}
void tarjan(const int &x,const int &par) {
    static int low[N],dfn[N],dep[N],cnt;
    ::par[x]=par;
    dep[x]=dep[par]+1;
    low[x]=dfn[x]=++cnt;
    for(unsigned i=0;i<e[x].size();i++) {
        const int &y=e[x][i];
        if(y==par) continue;
        if(!dfn[y]) {
            tarjan(y,x);
            low[x]=std::min(low[x],low[y]);
        } else {
            low[x]=std::min(low[x],dfn[y]);
        }
        if(dfn[x]<low[y]) {
            ans=std::max(ans,far[x]+far[y]+1);
            far[x]=std::max(far[x],far[y]+1);
        }
    }
    for(register unsigned i=0;i<e[x].size();i++) {
        const int &y=e[x][i];
        if(x!=::par[y]&&dfn[x]<dfn[y]) {
            dp(x,y,dep[y]-dep[x]+1);
        }
    }
}
int main() {
    getint();
    for(register int m=getint();m;m--) {
        for(register int k=getint(),u=getint();--k;) {
            const int v=getint();
            add_edge(u,v);
            u=v;
        }
    }
    tarjan(1,0);
    printf("%d
",ans);
    return 0;
}