A8367 | Tree or not Tree
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
You are given an undirected connected graph $G$ consisting of $n$ vertexes and $n$ edges. $G$ contains no self-loops or multiple edges. Let each edge has two states: on and off. Initially all edges are switched off.
You are also given $m$ queries represented as $(v,u)$ — change the state of all edges on the shortest path from vertex $v$ to vertex $u$ in graph $G$ . If there are several such paths, the lexicographically minimal one is chosen. More formally, let us consider all shortest paths from vertex $v$ to vertex $u$ as the sequences of vertexes $v,v_{1},v_{2},...,u$ . Among such sequences we choose the lexicographically minimal one.
After each query you should tell how many connected components has the graph whose vertexes coincide with the vertexes of graph $G$ and edges coincide with the switched on edges of graph $G$ .
You are also given $m$ queries represented as $(v,u)$ — change the state of all edges on the shortest path from vertex $v$ to vertex $u$ in graph $G$ . If there are several such paths, the lexicographically minimal one is chosen. More formally, let us consider all shortest paths from vertex $v$ to vertex $u$ as the sequences of vertexes $v,v_{1},v_{2},...,u$ . Among such sequences we choose the lexicographically minimal one.
After each query you should tell how many connected components has the graph whose vertexes coincide with the vertexes of graph $G$ and edges coincide with the switched on edges of graph $G$ .
输入格式
The first line contains two integers $n$ and $m$ ( $3<=n<=10^{5}$ , $1<=m<=10^{5}$ ). Then $n$ lines describe the graph edges as $a$ $b$ ( $1<=a,b<=n$ ). Next $m$ lines contain the queries as $v$ $u$ ( $1<=v,u<=n$ ).
It is guaranteed that the graph is connected, does not have any self-loops or multiple edges.
It is guaranteed that the graph is connected, does not have any self-loops or multiple edges.
输出格式
Print $m$ lines, each containing one integer — the query results.
输入输出样例
输入 #1
5 2 2 1 4 3 2 4 2 5 4 1 5 4 1 5
输出 #1
3 3
输入 #2
6 2 4 6 4 3 1 2 6 5 1 5 1 4 2 5 2 6
输出 #2
4 3
Let's consider the first sample. We'll highlight the switched on edges blue on the image.
- The graph before applying any operations. No graph edges are switched on, that's why there initially are 5 connected components.
- The graph after query $v=5,u=4$ . We can see that the graph has three components if we only consider the switched on edges.
- The graph after query $v=1,u=5$ . We can see that the graph has three components if we only consider the switched on edges.
Lexicographical comparison of two sequences of equal length of $k$ numbers should be done as follows. Sequence $x$ is lexicographically less than sequence $y$ if exists such $i$ ( $1<=i<=k$ ), so that $x_{i}<y_{i}$ , and for any $j$ ( $1<=j<i$ ) $x_{j}=y_{j}$ .
- The graph before applying any operations. No graph edges are switched on, that's why there initially are 5 connected components.
- The graph after query $v=5,u=4$ . We can see that the graph has three components if we only consider the switched on edges.
- The graph after query $v=1,u=5$ . We can see that the graph has three components if we only consider the switched on edges.
Lexicographical comparison of two sequences of equal length of $k$ numbers should be done as follows. Sequence $x$ is lexicographically less than sequence $y$ if exists such $i$ ( $1<=i<=k$ ), so that $x_{i}<y_{i}$ , and for any $j$ ( $1<=j<i$ ) $x_{j}=y_{j}$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted