[ZJOI2004]嗅探器 (割点)

这题就比较好玩吧水题
以数据范围来看随便怎么做就能过

\(O(n)\)显然我们得过一个割点，其次这个割点得在\(x-y\)中间且不为始终点

其他都好说，在中间：从\(x\)开始遍历，首先得保证\(x-y\)不是同一个点双，然后求中间的割点就好了\(dfn[v]≤dfn[y]\)，

#include<bits/stdc++.h>
using namespace std;
typedef int LL;
const LL maxn=1e6+9,inf=0x3f3f3f3f;
struct node{
    LL to,nxt;
}dis[maxn];
LL num,n,tim,ans,x,y;
LL head[maxn],dfn[maxn],low[maxn];
inline void Add(LL u,LL v){
    dis[++num]=(node){v,head[u]}; head[u]=num;
}
void Tarjan(LL u){
    dfn[u]=low[u]=++tim;
    for(LL i=head[u];i;i=dis[i].nxt){
        LL v(dis[i].to);
        if(!dfn[v]){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
            if(u!=x && u!=y && low[v]>=dfn[u] && dfn[v]<=dfn[y] && low[y]>=dfn[x])
                ans=min(ans,u);
        }
        low[u]=min(low[u],dfn[v]);
    }
}
int main(){
    cin>>n;
    LL u,v;
    while(scanf("%d%d",&u,&v) && u){
        Add(u,v);
        Add(v,u);
    }
    cin>>x>>y;
    ans=inf;
    Tarjan(x);
    if(ans==inf) cout<<"No solution";
    else cout<<ans;
    return 0;
}

[ZJOI2004]嗅探器 (割点)

原文：https://www.cnblogs.com/y2823774827y/p/10580648.html