#P14867. [OOI2024 资格赛]Legs warm-up exercise腿部热身练习

    ID: 14083 传统题 6000ms 512MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>CF3300NOI/NOI+/CTSLink-Cut Tree动态 DP实链/虚链维护动态路径聚合Splay标记复合

[OOI2024 资格赛]Legs warm-up exercise腿部热身练习

题目描述

在国家 X 中,有 nn 座城市和 mm 条道路。道路集合有两个有趣的性质:

  1. 所有道路都是单向道路;
  2. 如果忽略道路方向,把所有道路看成无向边,那么任意两座城市之间最多只有一条简单路径。

因此,忽略方向后,这张图是一片森林:在每个连通分量中,边数比点数少 11。

定义函数 cost(u,v)cost(u,v) 如下:

  • 如果存在从 uu 到 vv 的有向路径,那么 cost(u,v)cost(u,v) 等于这条路径上的道路数量;
  • 如果不存在从 uu 到 vv 的有向路径,那么 cost(u,v)=0cost(u,v)=0。

国家地图的美观度定义为:

∑u=1n∑v=1ncost(u,v).\sum_{u=1}^{n}\sum_{v=1}^{n} cost(u,v).

政府希望计算当前地图的美观度,并处理 qq 次修改。每次修改后,都需要重新输出地图美观度。

修改有四种类型:

  1. 添加一条从城市 uu 到城市 vv 的道路。
  2. 删除城市 uu 和城市 vv 之间的道路。
  3. 反转城市 uu 和城市 vv 之间道路的方向。
  4. 将从城市 uu 到城市 vv 的路径上的所有道路都定向为从 uu 指向 vv。保证忽略方向后,uu 到 vv 之间存在路径,所以这个操作可行。

保证每次修改后,城市和道路组成的无向图仍然是一片森林。

注意,本题中的询问会真正修改地图,后续询问基于前面修改后的结果。

输入格式

第一行包含一个整数 gg(0≤g≤100 \le g \le 10),表示测试组编号。

第二行包含三个整数 n,m,qn,m,q(2≤n≤4000002 \le n \le 400000,0≤m<n0 \le m < n,1≤q≤4000001 \le q \le 400000),分别表示城市数、初始道路数和修改次数。

接下来 mm 行,每行包含两个整数 u,vu,v(1≤u,v≤n1 \le u,v \le n),表示初始地图中有一条从 uu 到 vv 的有向道路。

接下来 qq 行,每行包含三个整数 t,u,vt,u,v(1≤t≤41 \le t \le 4,1≤u,v≤n1 \le u,v \le n),表示一次修改的类型和相关顶点。

输出格式

第一行输出初始地图的美观度。

接下来 qq 行,每行输出一次修改后的地图美观度。

样例 #1

样例输入 #1

0
5 4 4
1 2
2 3
3 4
4 5
3 4 3
2 3 2
1 4 2
4 1 4

样例输出 #1

20
6
3
4
16

样例解释

初始图,城市 1,2,3,4,51,2,3,4,5 形成一条路径,边方向依次为 1→2→3→4→51\to2\to3\to4\to5。

例如,cost(1,2)=cost(2,3)=cost(3,4)=cost(4,5)=1cost(1,2)=cost(2,3)=cost(3,4)=cost(4,5)=1,因为这些点对之间有直接道路。类似地,cost(1,3)=cost(2,4)=cost(3,5)=2cost(1,3)=cost(2,4)=cost(3,5)=2,因为需要经过两条道路才能到达。另一方面,例如 cost(2,1)=cost(4,1)=cost(5,3)=0cost(2,1)=cost(4,1)=cost(5,3)=0,因为后者不能从前者到达。对所有有序点对求和,得到 2020。

第一次修改需要反转城市 33 和城市 44 之间道路的方向。原来方向是 3→43\to4,修改后变为 4→34\to3。此时答案为 66。

此处应插入原题图:第一次修改后的图。

接着删除城市 22 与城市 33 之间的道路。此时答案为 33。

之后添加一条从城市 44 到城市 22 的道路。此时答案为 44。

第三次修改后的图。

最后,将城市 11 到城市 44 路径上的所有道路都定向为从 11 指向 44。此时答案为 1616。

此处应插入原题图:第四次修改后的图。

评分方式

测试数据包含 10 个测试组。只有通过该组以及若干指定的前置测试组,才能获得该组分数。Offline-testing 表示该组结果只会在比赛结束后公布。

组别 分数 附加限制 n,m,qn,m,q 修改类型限制 依赖组 备注
0 - - - 样例
1 10 n,m,q≤100n,m,q \le 100 0 -
2 8 n,m,q≤5000n,m,q \le 5000 0,1
3 11 n,m,q≤100000n,m,q \le 100000 只有类型 1 -
4 7 类型 1,2 3
5 13 只有类型 3 -
6 9 类型 3,4 5
7 12 - - 除类型 4 修改外,总有 $
8 18 0-7 -
9 6 n,m,q≤200000n,m,q \le 200000 0-8 Offline-testing
10 - 0-9