UOJ Logo Universal Online Judge

UOJ

#158. 【清华集训2015】静态仙人掌

Statistics

在OI的上古时代,流传着这样一个故事:

有一天,小W到森林里游玩,回来之后跟小V说,我发现好多棵会动的树耶!小V说,这有什么好稀奇的,我用手指头就能维护每棵树的形态。

于是又过了几天小W到沙漠里游玩,回来之后跟小V说,我发现好多棵会动的仙人掌耶!小V说,这有什么好稀奇的,我用脚丫子就能维护每棵仙人掌的形态。

小S看到了这段故事,深受感动。他决定一步步做起,从仙人掌做起,从不会动的仙人掌做起。

本题中,我们定义:

什么是仙人掌

如果一个无向连通图的任意一条边最多属于一个简单环,且不存在自环,我们就称之为仙人掌。

仙人掌上的两点间最短路径(一定是简单路径)与最长简单路径的定义与一般无向图的定义相同。

本题中,我们还保证任何一个简单环的长度均为奇数。这意味着不存在重边,并且任意两点间的最短路径与最长简单路径一定是唯一的。

为了证明你确实能够维护仙人掌,我们给你 $n$ 个结点,从 $1$ 到 $n$ 标号,其中 $1$ 号点是仙人掌的根。它有 $m$ 条边,第 $i$ 条边连接了结点 $u_i$ 与 $v_i$。

每个结点有一个颜色(黑或白),初始时均为黑色。现在有 $q$ 次操作,每次操作格式为 $op$ $x$($1 \leq op \leq 3, 1 \leq x \leq n$):

  • 若$op=1$,表示将点$x$到根的最短路径上的所有点的状态取反(黑变白,白变黑);
  • 若$op=2$,表示将点$x$到根的最长简单路径上的所有点的状态取反;
  • 若$op=3$,表示询问点$x$的子仙人掌中的黑点数目。点 $x$ 的子仙人掌定义为:删除从根到点 $x$ 的所有简单路径上的所有边后,点 $x$ 所在的连通块。

输入格式

第一行三个用空格隔开的正整数 $n,m,q$ 表示一共有 $n$ 个结点,$m$ 条边,$q$ 个操作。

接下来 $m$ 行,每行两个空格隔开的正整数 $u_i, v_i$,表示一条边。

接下来 $q$ 行,每行表示一个操作,格式如上述。

输出格式

对于每个 $op=3$ 的操作,输出一行相应的结果。

样例一

input

7 9 11
1 2
1 3
2 3
3 4
3 5
4 5
5 6
5 7
6 7
3 1
3 2
3 3
1 7
3 1
3 2
3 3
2 7
3 1
3 2
3 3

output

7
1
5
3
1
2
4
0
3

样例二

见样例数据下载。这组数据符合子任务4的限制与约定。

样例三

见样例数据下载。这组数据符合子任务5的限制与约定。

样例四

见样例数据下载。这组数据符合子任务6的限制与约定。

限制与约定

本题使用捆绑测试。每个子任务有若干个测试点,分为 $8$ 个子任务,你只有通过一个子任务的所有测试点才能得到这个子任务的分数。

前七个子任务的限制

时间限制:$1\texttt{s}$。

空间限制:$768\texttt{MB}$。

$n, q \leq 50000$。

子任务1(7分)

$n \leq 2, q \leq 2000$。

子任务2(14分)

$n \leq 20, q \leq 2000$。

子任务3(9分)

$n, q \leq 2000$。

子任务4(17分)

保证 $m=n-1$,并且 $u_i=i,v_i=i+1$,且不存在 $op=2$ 的操作。

子任务5(14分)

保证 $m=n-1$,并且 $u_i < v_i$,且不存在 $op=2$ 的操作。

子任务6(11分)

保证不存在 $op=2$ 的操作。

子任务7(18分)

没有特殊的限制与约定。

子任务8(10分)

空间限制缩小为 $128\texttt{MB}$。

下载

样例数据下载