P8531 [Ynoi2003] Xu-Hai Comet

Define a graph as a “sea urchin” if it satisfies all of the following conditions: 1. It is a connected graph. 2. It contains exactly one simple cycle. 3. For every vertex not on the cycle, its degree is at most $2$. There is a graph with $n$ vertices and $n$ edges. The $i$-th edge connects $u_i$ and $v_i$ (the graph is not guaranteed to be connected). Define the interval subgraph $[l,r]$ of a graph as $(V',E')$, where $E'=\{(u_i,v_i)\mid l\leq i\leq r\}$, $V'=\{u_i\mid l\leq i\leq r\} \cup \{v_i\mid l\leq i\leq r\}$. That is, this interval subgraph contains exactly the edges in the interval and all vertices that appear in at least one edge in the interval. Now there are $q$ queries. Each query gives an interval $l,r$. For this $l,r$, compute how many sub-intervals $[l',r']\ (l\leq l'\leq r'\leq r)$ satisfy that the interval subgraph $[l',r']$ of the original graph is a sea urchin. **Additional notes for Condition 2:** 1. A simple cycle means: you can start from any vertex, traverse some non-repeated edges, and return to the start vertex; you must traverse at least one edge; and you do not visit any repeated vertex except that the start and end vertex are the same. For example, $1-2-3-1$ is a simple cycle. Two parallel edges $1-2$ also form a simple cycle. But a graph with only one vertex is not. Also, $1-2-3-4-5-3-1$ is not a simple cycle. (Here the cycle is written as a path starting from some vertex.) 2. Condition $2$ also requires that, besides the cycle edges, there is no edge whose both endpoints are on this cycle.

The first line contains an integer $n$, meaning the number of vertices and the number of edges. The next $n$ lines each contain two integers $u_i,v_i$, describing an edge. The next line contains an integer $q$. The next $q$ lines each contain two integers $l,r$, describing a query.

Output $q$ lines, each containing one number, the answer to the corresponding query.

Idea: lk&nzhtl1477, Solution: lk&ccz181078, Code: lk&ccz181078, Data: lk&ccz181078. **The testdata guarantees that there are no self-loops.** | Subtask ID | $n\le$ | $q\le$ | Special Property | Score | | :--------: | :-----: | :-----: | :--------------: | :---: | | $1$ | $100$ | $100$ | None | $5$ | | $2$ | $500$ | $500$ | None | $15$ | | $3$ | $5000$ | $5000$ | None | $15$ | | $4$ | $50000$ | $50000$ | None | $15$ | | $5$ | $10^6$ | $1$ | None | $15$ | | $6$ | $10^6$ | $10^6$ | The original graph is a sea urchin | $15$ | | $7$ | $10^6$ | $10^6$ | None | $20$ | Translated by ChatGPT 5