题目大意：
给你一个仙人掌，求图中相距最远的点对之间的距离。思路：
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可能会重复。1 #include2 #include 3 #include 4 #include 5 inline int getint() { 6 register char ch; 7 while(!isdigit(ch=getchar())); 8 register int x=ch^'0'; 9 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');10 return x;11 }12 const int N=50001;13 std::vector e[N];14 int far[N],par[N],ans;15 inline void add_edge(const int &u,const int &v) {16 e[u].push_back(v);17 e[v].push_back(u);18 }19 inline void dp(const int &top,const int &end,const int &size) {20 static int cir[N*2];21 static std::deque q;22 for(register int i=size,v=end;i;i--) {23 cir[size+i]=cir[i]=far[v];24 v=par[v];25 }26 q.push_back(1);27 for(register int i=2;i<=size*2;i++) {28 if(i-q.front()>size/2) q.pop_front();29 ans=std::max(ans,cir[i]+cir[q.front()]+i-q.front());30 while(!q.empty()&&cir[q.back()]-q.back()<=cir[i]-i) q.pop_back();31 q.push_back(i);32 }33 q.clear();34 for(register int i=2;i<=size;i++) {35 far[top]=std::max(far[top],cir[i]+std::min(i-1,size-i+1));36 }37 }38 void tarjan(const int &x,const int &par) {39 static int low[N],dfn[N],dep[N],cnt;40 ::par[x]=par;41 dep[x]=dep[par]+1;42 low[x]=dfn[x]=++cnt;43 for(unsigned i=0;i