UOJ Logo Universal Online Judge

UOJ

#189. 【集训队互测2016】火车司机出秦川

附件下载 统计

火车司机出秦川,跳蚤国王下江南。每天,勤劳的火车司机们都会开着自己心爱的火车去传播福音。

和跳蚤国类似,火车国也有 $n$ 个城市编号为 $1$ 到 $n$,城市之间有一些铁路相连。这些铁路构成了一个仙人掌。如果一个无向连通图的任意一条边最多属于一个简单环,我们就称之为仙人掌。所谓简单环即不经过重复的结点的环。

什么是仙人掌

第 $i$ 天会有 $k_i$ 名火车司机出秦川,第 $j$ 名司机会从城市 $s_j$ 到 $t_j$。有一些司机是老司机,他们会沿着选择经过城市最多的路径走,显示自己高超的驾驶技术。而另一些是新司机,他们会走经过城市最少的路径。但不管是新司机还是老司机,都不会走过同一个城市两次(也就是选择的路径都是简单路径)。

每一条铁路周围都有一些人居住,如果第 $i$ 天这条铁路被火车司机经过,这些人会收到福音。我们想知道每天有多少人收到福音。

当然人口是会变化的,第 $i$ 天结束以后第 $w_i$ 铁路的人口会改变为 $x_i$。

输入格式

第一行三个整数 $n,m$ 和 $q$,表示有 $n$ 个城市,有 $m$ 条铁路以及有 $q$ 天。

接下来 $m$ 行每行三个整数 $u,v,w$,表示一条连接 $u$ 和 $v$ 的铁路,铁路周围有 $w$ 个人。保证是仙人掌,没有自环,每个环的长度都是奇数。铁路编号从 $1$ 开始。

接下来 $2q$ 行,每两行表示一天。

第一行一个整数 $k_i$ 表示有 $k_i$ 名司机( $k_i$ 可能为 $0$ ,这时候请忽略这个询问并输出 $0$ ),然后是 $3k_i$ 个整数 $s_j,t_j,type_j$,分别表示每个司机的起点和终点和类型,如果 $type_j$ 是 $0$ 表示是新司机,为 $1$ 是老司机。每个司机的起点和终点均不同。

第二行两个整数 $w_i$ 和 $x_i$,表示第 $w_i$ 条铁路的人口会改变为 $x_i$ ,如果 $w_i$ 为 $0$ 则表示没有修改。

输出格式

$q$ 行,每行一个整数表示这一天收到福音的人数。

样例一

input

11 13 3
1 2 1
2 3 2
1 3 4
2 8 8
2 9 16
9 10 32
10 11 64
11 9 128
3 4 256
3 5 512
4 7 1024
7 6 2048
5 6 4096
1 10 7 1
3 8192
3 8 1 1 2 7 1 10 4 0
7 16384
3 8 1 0 2 7 0 10 4 1
0 16384

output

6869
15163
32667

样例二

见样例数据下载。

样例三

见样例数据下载。

限制与约定

保证任意时刻边长和都属于int范围内。边长均为正整数。

$2 \leq n \leq 300000$, $n-1 \leq m \leq 2n-2,q \leq 300000$,令 $S = \sum k_i$, $S<=300000$。

具体数据范围见下表:

数据编号 $n$ 的规模 $q$ 的规模 $S$ 的规模 其他
1$n = 2$$q \leq 10$$S \leq 10$
2$n = 100$$q \leq 100$$S \leq 100$
3$n = 100000$$q \leq 100000$$S \leq 100000$$m=n-1$,没有修改
4$m=n-1$
5$n = 300000$$q \leq 300000$$S \leq 300000$$m=n-1$,没有修改
6$m=n-1$
7$n = 100000$$q \leq 100000$$S \leq 100000$没有修改
8
9$n = 300000$$q \leq 300000$$S \leq 300000$没有修改
10

时间限制:$5\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载

IOI赛制

本题在考试时排行榜上显示的成绩即为最终评测结果。