rt 找了好久错误都看不出来 , 一直50分 , 后面改的连变量都感觉和第一篇题解都差不多了啊。。。 求大佬帮助qwq
#include<bits/stdc++.h>
using namespace std ;
#define maxn 700010
//#define int long long
#define kkk signed main
int read(){
int ans = 0 , f = 1 ; char ch = getchar() ;
while ( ch < '0' || ch > '9') { if( ch == '-' ) f = -1 ; ch = getchar() ; }
while ( ch >= '0' && ch <= '9' ) ans = ( ans << 3 ) + ( ans << 1 ) + ch - '0' , ch = getchar() ;
return ans * f ;
}
int dfn[maxn] , low[maxn] , calc ;
int w[maxn] , dep[maxn] , son[maxn] , siz[maxn] , top[maxn] , fa[maxn];
int n , m , q , tot ;
//int head[maxn] , to[maxn] , nxt[maxn] ;
int st[maxn] , tp ;
struct Graph{
int head[maxn << 1] , to[maxn << 1] , nxt[maxn << 1], cnt = 0 ;
void addedge(int u , int v){
to[++cnt] = v ;
nxt[cnt] = head[u] ;
head[u] = cnt;
to[++cnt] = u ;
nxt[cnt] = head[v] ;
head[v] = cnt ;
}
} G , T ;
void tarjan(int u ){
dfn[u] = low[u] = ++calc ; st[++tp] = u ;
for(int i = G.head[u] ; i ; i = G.nxt[i]){
int v = G.to[i] ;
if(!dfn[v]){
tarjan(v) ;
low[u] = min(low[u] , low[v]) ;
if(low[v] >= dfn[u]){
T.addedge(++tot , u) ;
printf("tot : %lld u : %lld \n" , tot , u) ;
int x = 0 ;
do{
x = st[tp--] ; T.addedge(tot , x) ; //
}while(x!=v);
}
}
else low[u] = min(low[u] , dfn[v]) ;
}
}
void dfs1(int u , int dp){
// printf("u : %lld dp : %lld\n" , u , dp) ;
siz[u] = 1 , dep[u] = dp ;
int maxson = 0 ;// printf("T : %lld \n" , T.head[u]) ;
for(int i = T.head[u]; i ; i = T.nxt[i]){
int v = T.to[i] ;
if(siz[v]) continue ;
fa[v] = u ;
dfs1(v ,dp + 1) ;
siz[u] += siz[v] ;
if(siz[v] > maxson) son[u] = v , maxson = siz[v] ;
}
}
void dfs2(int u , int tp){
top[u] = tp ;
// printf("u : %lld \n" , u) ;
// printf("u ; %lld tp : %lld \n" , u , tp) ;
if(son[u]) dfs2(son[u] , tp) ;
for(int i = T.head[u] ; i ; i = T.nxt[i]){
int v = T.to[i] ;
// printf(" u : %lld v : %lld \n" , u , v) ;
if(v == son[u] || v == fa[u]) continue ;
dfs2(v , v) ;
}
}
inline int query(int a , int b){
while(top[a] != top[b]){
if(dep[top[a]] < dep[top[b]]) swap(a , b) ;
a = fa[top[a]] ;
}
return dep[a] < dep[b] ? a : b ;
}
kkk(){
// freopen("1.in" , "r" , stdin) ;
// freopen("1.out" , "w" , stdout) ;
n =read() , m = read() ;
tot = n ;
int u , v ;
for(int i = 1 ; i <= m ; i++){
u = read() , v = read() ;
G.addedge(u , v) ;
}
tarjan(1) ;
dfs1(1 , 1) ;
dfs2(1 , 1) ;
int lca ;
q = read() ;
while(q--){
u = read() , v = read() ;
lca = query(u , v) ;
// printf("u : %lld dep : %lld v: %lld dep : %lld \n" , u ,dep[u] , v , dep[v]) ;
// printf("lca : %lld dep : %lld \n" , lca , dep[lca]) ;
//
printf("%d\n" , (dep[u] + dep[v] - 2 * dep[lca])/2 + 1) ;
}
// for(int i = 1 ; i <= tot ; i++){
// printf("fa[%lld] :%d dep : %d top : %d \n" , i , fa[i] , dep[i] , top[i]) ;
// }
return 0 ;
}