[ZJOI2004]嗅探器

Link
2004年的水题，10分钟就过了…我也不知道为什么难度是省选/NOI-，可能是恶意评分吧。
很简单，这个节点一定在两个中心节点中间的割点上。
然后我们还有两个需要判断的东西：

$Dfn[T] >= Dfn[E[i].T]$
啥意思呢，就是说$T$，也就是我们在这两个中心节点中选的一个当做终点，要在$E[i].T$之后被搜到，这样可以保证使得$Now$是必经之路。

$Low[T] >= Dfn[Now]$
也就是保证要经过$Now$点。
以上两个都是为了确保$Now$是两个中心节点的必经之路。
然后还要记得判断一下$Now != S && Now != T$，不在两个中心节点上。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

typedef long long LL ;
const int MAXN = 5010 ;
const int MAXM = 5010 ;
const int Inf = 100000000 ;

int N, M, Dfn[MAXN], Low[MAXN], Tot, H[MAXN], Ken ;
bool Cut[MAXN] ; int S, T, Ans = Inf ;
struct Node {
    int F, T, Next ;
}   E[MAXN << 1] ;

inline int Read() {
    int X = 0, F = 1 ; char ch = getchar() ;
    while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
    while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
    return X * F ;
}

inline void Add (int F, int T) {
    E[++ Tot].F = F, E[Tot].T = T, E[Tot].Next = H[F], H[F] = Tot ;
}

inline void Tarjan(int Now) {
    Dfn[Now] = Low[Now] = ++ Ken ;
    for (int i = H[Now] ; i ; i = E[i].Next) {
        if (! Dfn[E[i].T]) {
            Tarjan(E[i].T) ; 
            Low[Now] = min(Low[E[i].T], Low[Now]) ;
            if (Now != S && Now != T)
            if (Dfn[Now] <= Low[E[i].T])
            if (Dfn[E[i].T] <= Dfn[T])
            if (Dfn[S] <= Low[T]) 
                Ans = min(Ans, Now) ;
        }   Low[Now] = min(Low[Now], Dfn[E[i].T]) ;
    }
}

int main() {
    cin >> N ; int A, B ;
    do {
        cin >> A >> B ;
        Add(A, B) ; Add(B, A) ;
    }   while (A + B) ;
    cin >> S >> T ; 
    Tarjan(S) ;
    if (Ans == Inf) puts("No solution") ;
    else {printf("%d", Ans) ;} return 0 ;
}