Edge Queries (Codeforces 1763F)
Tags: DP, dsu

You are given an undirected, connected graph of $$$n$$$ nodes and $$$m$$$ edges. All nodes $$$u$$$ of the graph satisfy the following:  Let $$$S_u$$$ be the set of vertices in the longest simple cycle starting and ending at $$$u$$$.  Let $$$C_u$$$ be the union of the sets of vertices in any simple cycle starting and ending at $$$u$$$.  $$$S_u = C_u$$$. You need to answer $$$q$$$ queries.For each query, you will be given node $$$a$$$ and node $$$b$$$. Out of all the edges that belong to any simple path from $$$a$$$ to $$$b$$$, count the number of edges such that if you remove that edge, $$$a$$$ and $$$b$$$ are reachable from each other.

Input: The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le \min$$$($$$2 \cdot 10^5$$$, $$$(n \cdot (n-1))/2$$$)) — the total number of nodes and edges in the graph, respectively.The next $$$m$$$ lines contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le$$$ $$$u$$$, $$$v$$$ $$$\le n$$$, $$$u \neq v$$$) — describing an edge, implying that nodes $$$u$$$ and $$$v$$$ are connected to each other.It is guaranteed that there is at most one edge between any pair of vertices in the graph and the given graph is connected.The next line contains a single integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.Then $$$q$$$ lines follow, each representing a query. Each query contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le$$$ $$$a$$$, $$$b$$$ $$$\le n$$$).

Output: For each query, output a single integer — answer to the query.

Note: The graph in the first sample is :   The first query is $$$(1, 4)$$$. There are $$$5$$$ total edges that belong to any simple path from $$$1$$$ to $$$4$$$. Edges $$$(3, 4), (4, 5), (5, 3)$$$ will be counted in the answer to the query.The fourth query is $$$(2, 8)$$$. There is only one simple path from $$$2$$$ to $$$8$$$, thus none of the edges will be counted in the answer to the query.The fifth query is $$$(7, 10)$$$. There are $$$4$$$ total edges that belong to any simple path from $$$7$$$ to $$$10$$$, all of them will be counted in the answer to the query.

Sample Inputs:
10 11
1 2
2 3
3 4
4 5
5 3
2 7
7 9
9 10
10 6
6 7
1 8
5
1 4
5 10
3 5
2 8
7 10

13 15
1 2
2 3
3 4
4 1
2 4
3 5
5 6
6 7
6 8
7 9
9 10
8 7
10 11
10 12
10 13
6
9 11
1 5
1 8
5 2
5 12
12 13

Sample Outputs:
3
7
3
0
4

0
5
8
5
3
0

Solution (Python):
import sys
input = sys.stdin.buffer.readline
MAXP = 0
ancestor = [[]]
tin = []
tout = []

def set_up(root=1):
    global MAXP, ancestor, tin, tout
    while 1 << MAXP + 1 <= n - 2:
        MAXP += 1
    ancestor = [[0] * (MAXP + 1) for _ in range(n + 1)]
    tin = [0] * (n + 1)
    tout = [0] * (n + 1)
    t = 0
    vis = [0] * (n + 1)
    s = [root]
    true_s = []
    while s:
        c = s[-1]
        if not vis[c]:
            vis[c] = 1
            true_s.append(c)
            tin[c] = t
            t += 1
            p = root
            if len(true_s) >= 2:
                p = true_s[-2]
            ancestor[c][0] = p
            for i in range(1, MAXP + 1):
                ancestor[c][i] = ancestor[ancestor[c][i - 1]][i - 1]
            for ne in adj[c]:
                if ne != p:
                    s.append(ne)
        else:
            if true_s and true_s[-1] == c:
                tout[c] = t
                t += 1
                true_s.pop()
            s.pop()

def is_ancestor(u, v):
    return tin[u] <= tin[v] and tout[v] <= tout[u]

def lca(u, v):
    if is_ancestor(u, v):
        return u
    elif is_ancestor(v, u):
        return v
    else:
        for i in range(MAXP, -1, -1):
            if not is_ancestor(ancestor[u][i], v):
                u = ancestor[u][i]
        return ancestor[u][0]

def just_before(u, v):
    for i in range(MAXP, -1, -1):
        if not is_ancestor(ancestor[u][i], v):
            u = ancestor[u][i]
    return u

class Comps:

    def __init__(self, n):
        self.n = n + 1
        self.size = [1] * self.n
        self.par = [i for i in range(self.n)]
        self.first = [i for i in range(self.n)]
        self.edges = [0] * self.n

    def comp(self, a):
        if self.par[a] == a:
            return a
        self.par[a] = self.comp(self.par[a])
        return self.par[a]

    def merge(self, a, b):
        a = self.comp(a)
        b = self.comp(b)
        if a != b:
            if self.size[a] < self.size[b]:
                (a, b) = (b, a)
            self.par[b] = a
            self.size[a] += self.size[b]
            self.edges[a] += self.edges[b] + 1
            if tin[self.first[b]] < tin[self.first[a]]:
                self.first[a] = self.first[b]
(n, m) = map(int, input().split())
adj = [[] for i in range(n + 1)]
for _ in range(m):
    (u, v) = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)
set_up()
comps = Comps(n)
vis = [0] * (n + 1)
s = [1]
true_s = []
on_true_s = [0] * (n + 1)
while s:
    c = s[-1]
    if not vis[c]:
        vis[c] = 1
        true_s.append(c)
        on_true_s[c] = 1
        for ne in adj[c]:
            s.append(ne)
    else:
        if true_s and true_s[-1] == c:
            true_s.pop()
            on_true_s[c] = 0
        elif on_true_s[c] and true_s[-2] != c:
            for i in range(len(true_s) - 1, -1, -1):
                comps.merge(true_s[i], true_s[i - 1])
                if comps.comp(true_s[i - 1]) == comps.comp(c):
                    break
            comps.edges[comps.comp(c)] += 1
        s.pop()
root_ans = [0] * (n + 1)
vis = [0] * (n + 1)
s = [(1, 0)]
while s:
    (c, p) = s.pop()
    if not vis[c]:
        vis[c] = 1
        root_ans[c] = root_ans[p]
        if comps.comp(c) == comps.comp(p) and comps.first[comps.comp(p)] == p:
            root_ans[c] += comps.edges[comps.comp(p)]
        for ne in adj[c]:
            if ne != p:
                s.append((ne, c))
ans = []
q = int(input())
for _ in range(q):
    (a, b) = map(int, input().split())
    c = lca(a, b)
    query_ans = root_ans[a] + root_ans[b] - 2 * root_ans[c]
    if c != comps.first[comps.comp(c)]:
        in_comp = False
        for end in (a, b):
            if end != c:
                if comps.comp(c) == comps.comp(just_before(end, c)):
                    in_comp = True
        if in_comp:
            query_ans += comps.edges[comps.comp(c)]
    ans.append(query_ans)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys
import os
from io import BytesIO, IOBase
from _collections import deque
from math import ceil, log2
from collections import Counter
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
if sys.version_info[0] < 3:
    sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
else:
    (sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
file = sys.stdin
if os.environ.get('USER') == 'loic':
    file = open('data.in')
line = lambda : file.readline().split()
ui = lambda : int(line()[0])
mi = lambda : map(int, line())
li = lambda : list(mi())

class LCA_Binary_Lifting:

    def __init__(self, g, start, edges):
        sz = len(g)
        self.lg = ceil(log2(sz))
        self.level = [0] * sz
        self.nb = [0] * sz
        self.ent = [0] * sz
        self.out = [0] * sz
        c_ent = 0
        c_out = 0
        self.par = [[] for _ in range(sz)]
        self.par[start] = [start for _ in range(self.lg + 1)]
        self.edges = edges
        state = [-1] * len(g)
        q = deque([start])
        state[start] = 0
        self.nb[start] = self.edges[start]
        while q:
            n = q[-1]
            if state[n] == 0:
                self.ent[n] = c_ent
                c_ent += 1
            chs = g[n]
            if state[n] == 1:
                q.pop()
                self.out[n] = c_out
                c_out += 1
            else:
                for ch in chs:
                    if state[ch] == -1:
                        state[ch] = 0
                        q.append(ch)
                        self.level[ch] = self.level[n] + 1
                        self.nb[ch] = self.nb[n] + self.edges[ch]
                        self.par[ch].append(n)
                        for i in range(1, self.lg + 1):
                            self.par[ch].append(self.par[self.par[ch][i - 1]][i - 1])
                state[n] = 1

    def query(self, u, v):
        if self.is_ancestor(u, v):
            return u
        if self.is_ancestor(v, u):
            return v
        for i in range(self.lg, -1, -1):
            if not self.is_ancestor(self.par[u][i], v):
                u = self.par[u][i]
        return self.par[u][0]

    def is_ancestor(self, u, v):
        return self.ent[u] <= self.ent[v] and self.out[u] >= self.out[v]

    def distance(self, u, v):
        lca = self.query(u, v)
        return self.level[u] + self.level[v] - 2 * self.level[lca]

    def sum_nb(self, u, v):
        lca = self.query(u, v)
        return self.nb[u] + self.nb[v] - 2 * self.nb[lca] + self.edges[lca]

def squeeze_bi_connected(g, start):
    sz = len(g)
    seen = [-1] * sz
    lvl = [-1] * sz
    dp = [0] * sz
    par = [None] * sz
    gp = [-1] * sz
    mp = [-1] * sz
    edges = []
    up = [0] * sz
    q = deque([start])
    seen[start] = 0
    lvl[start] = 0
    dp[start] = -1
    mp[start] = start
    while q:
        n = q[-1]
        chs = g[n]
        while seen[n] != len(chs) and seen[chs[seen[n]]] != -1:
            seen[n] += 1
        if seen[n] == len(chs):
            q.pop()
            for ch in chs:
                dp[n] += 1 if lvl[ch] < lvl[n] else -1
                if lvl[ch] < lvl[n]:
                    up[n] += 1
            if gp[n] == -1:
                gp[n] = n
            if n != start:
                dp[par[n]] += dp[n]
                dp[n] -= 1
                if dp[n] != 0:
                    gp[par[n]] = gp[n]
                    up[par[n]] = up[n]
                else:
                    edges.append((n, par[n]))
                    up[n] -= 1
            mp[gp[n]] = n
        else:
            ch = chs[seen[n]]
            seen[ch] = 0
            q.append(ch)
            par[ch] = n
            lvl[ch] = lvl[n] + 1
    for n in range(len(g)):
        gp[n] = mp[gp[n]]
    cnt = Counter(gp)
    mp_idx = {k: i for (i, k) in enumerate(cnt.keys())}
    bcc = [[] for _ in range(sz + len(cnt))]
    for n in range(N):
        gp_n = gp[n]
        if gp_n == n:
            if cnt[n] == 1:
                for ch in g[n]:
                    bcc[n].append(ch)
                    bcc[ch].append(n)
            else:
                if n != start:
                    bcc[n].append(par[n])
                    bcc[par[n]].append(n)
                bcc[n].append(sz + mp_idx[gp_n])
    for n in range(N):
        gp_n = gp[n]
        if gp_n != n:
            bcc[sz + mp_idx[gp_n]].append(n)
            bcc[n].append(sz + mp_idx[gp_n])
    edges = [0] * (sz + len(cnt))
    for gp_n in cnt.keys():
        edges[sz + mp_idx[gp_n]] = up[gp_n]
    return (bcc, edges)

def solve():
    res = []
    (bcc, edges) = squeeze_bi_connected(G, 0)
    start = next((n for n in range(len(bcc)) if bcc[n]))
    lca = LCA_Binary_Lifting(bcc, start, edges)
    for _ in range(Q):
        (u, v) = mi()
        u -= 1
        v -= 1
        res.append(lca.sum_nb(u, v))
    return '\n'.join((str(v) for v in res))
for test in range(1, 1 + 1):
    (N, M) = mi()
    G = [[] for _ in range(N)]
    for _ in range(M):
        (u, v) = mi()
        u -= 1
        v -= 1
        G[u].append(v)
        G[v].append(u)
    Q = ui()
    print(solve())
file.close()

Solution (Python):
import re
import functools
import random
import sys
import os
import math
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heappushpop, heapify, heappop, heappush
from io import BytesIO, IOBase
from copy import deepcopy
import threading
from typing import *
from operator import add, xor, mul, ior, iand, itemgetter
import bisect
BUFSIZE = 4096
inf = float('inf')

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
(n, m) = MII()
path = [[] for _ in range(n)]
new_path = [[] for _ in range(2 * n)]
edges = []
for _ in range(m):
    (x, y) = GMI()
    path[x].append(y)
    path[y].append(x)
    edges.append([x, y])
stack = []
tmstamp = 0
node = n
dfn = [0] * n
low = [0] * n
col = [0] * n
pre = [0] * (n * 2)
depth = [0] * (n * 2)

@bootstrap
def tarjan(u, f):
    global tmstamp, node
    tmstamp += 1
    dfn[u] = low[u] = tmstamp
    stack.append(u)
    for v in path[u]:
        if dfn[v] == 0:
            yield tarjan(v, u)
            low[u] = min(low[u], low[v])
        elif v != f:
            low[u] = min(low[u], dfn[v])
    if low[u] == dfn[u]:
        while True:
            col[stack[-1]] = node
            new_path[stack[-1]].append(node)
            new_path[node].append(stack[-1])
            tmp = stack.pop()
            if tmp == u:
                break
        node += 1
    yield
tarjan(0, -1)
for (x, y) in edges:
    if col[x] == col[y]:
        pre[col[x]] += 1
    else:
        new_path[x].append(y)
        new_path[y].append(x)
father = [[-1] * 19 for _ in range(2 * n)]

@bootstrap
def dfs(u, f):
    depth[u] = depth[f] + 1
    if f != -1:
        pre[u] += pre[f]
    father[u][0] = f
    tmp = f
    for i in range(1, 19):
        if tmp == -1:
            break
        father[u][i] = father[tmp][i - 1]
        tmp = father[u][i]
    for v in new_path[u]:
        if v != f:
            yield dfs(v, u)
    yield
dfs(0, -1)

def lca(u, v):
    if u == v:
        return u
    if depth[u] < depth[v]:
        (u, v) = (v, u)
    delta = depth[u] - depth[v]
    for i in range(19):
        if delta & 1 << i:
            u = father[u][i]
    if u == v:
        return u
    for i in range(18, -1, -1):
        if father[u][i] != father[v][i]:
            u = father[u][i]
            v = father[v][i]
    return father[u][0]
q = II()
for _ in range(q):
    (x, y) = GMI()
    tmp = lca(x, y)
    if father[tmp][0] != -1:
        print(pre[x] + pre[y] - pre[tmp] - pre[father[tmp][0]])
    else:
        print(pre[x] + pre[y] - pre[tmp])