300614: CF117E. Tree or not Tree
Memory Limit:256 MB
Time Limit:5 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Tree or not Tree
题意翻译
G是一张由n个点和n条边组成的无向图。G中没有自环和重边。每条边有两种状态“开”和“关”。一开始,所有的边都是“关”着的。 现在有m个操作(v,u),表示将从v到u的最短路上的边改变状态(如果状态为“开”则变成“关”,反之,变成“开”)。如果v到u存在多条最短路,则我们选取点序列字典序最小的那一条。 比如,将所有从v到u的路径上的点表示成序列为 v,v1,v2,...,u 。那么我们从中取字典序最小的那一条。 在每一次操作后,你需要计算在图中由所有点和状态为“开”的边所组成图的连通块的数目。 样例解释: 在图中处于“开”状态的边我们用蓝色高亮表示。 在没有进行任何操作前,所有的边都是“关”,也就是说,一开始有5个连通块。 ![](https://img.51nod.com/upload/000FBF5D/08D2E0B74A2195DB0000000000000040.png ) 下图是执行了操作v=5,u=4后的图。如果我们关心“开”的边,可以看到有3个连通块。 ![](https://img.51nod.com/upload/000FBF5D/08D2E0B74A2195DB0000000000000041.png ) 然后执行操作v=1,u=5后,如下图。同样如果我们关心“开”的边,可以看到有3个连通块。 ![](https://img.51nod.com/upload/000FBF5D/08D2E0B753B4AE190000000000000042.png ) 两个长度为k的点序列比较方法如下。 存在两个序列x,y,长度都是k。 如果存在i(1≤i≤k)和任意j(1≤j<i)使得 xi<yi 并且 xj=yj ,那么我们就说x比y小。 Input 单组测试数据 第一行有两个整数,n和m(3≤n≤10^5,1≤m≤10^5). 接下来的n行, 每行有两个整数a,b(1≤a,b≤n)表示a到b有边相连。 再接下来有m行, 每行有两个整数v,u(1≤v,u≤n)表示一次操作,即要变化的路径的起点和终点。 所给定的图是连通的,里面没有自环,也没有重边。 Output 有m行,每行代表一次操作后,连通块数目。题目描述
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 $ .输入输出格式
输入格式
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.
输出格式
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