#1967. 公园

    ID: 1967 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest313来源:qoj.ac数据:公开样例动态规划

公园

公园

题目描述

标题: 公园 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

小 Q 是一名设计师,她主导着一个公园的设计。她已经设计好了每个景点的位置、内容,以及景点之间的路线。但是,对于如何设置景点周围的环境(主题),她就犯了难,因为对于有些道路,若两端的景点主题不一致,过渡会显得太突兀;对于另一些道路,若两端的景点一致,又会显得太单调;而且根据景点的内容,不同景点适合使用的主题也可能不同。她想通过一个程序来计算决定,哪些景点周围使用西部主题,哪些景点周围使用科幻主题,然而小 Q 的编程能力有限,所以她想让你帮忙解决这个问题。

公园有 n 个景点,m 条连接两个景点的无向道路。第 i 条道路连接第 xi 和第 yi 个景点。
若第 i 条道路两端的景点主题相同,可以得到 ci 的美观度;若第 i 条道路两端的景点主题不同,可以得到 di 的美观度。
第 i 个景点使用西部主题可以得到 wi 的美观度,使用科幻主题可以得到 si 的美观度。

公园的线路图是小 Q 精心设计的,小 Q 保证她设计的公园中从任意一个景点出发,能够到达所有的景点;保证每条道路连接的是两个不同的景点;保证没有两条不同的道路连接同一对景点;并且对于任意四个景点 A,B,C,D ,使得其中任意两条路径除公共端点外没有公共点,且这六条路径分别连接四个景点中的每一对景点—— AB,AC,AD,BC,BD,CD 。

以下给出一些一定不是小 Q 设计的公园线路图的例子:

你需要把每个景点的主题设定为科幻主题和西部主题中的一种,使得所有景点以及道路的美观度之和最大。

小 Q 可能会通过重新计算来修改某个景点的 wi 和 si 的值或者某条道路的 ci 和 di 的值。她会修改 Q 次,你需要在修改之前以及每一次修改之后输出最优方案的美观度之和。注意修改与修改之间不是互相独立的。

输入格式

第一行两个正整数 n,m 。

接下来 n 行,每行两个非负整数,其中第 i 行表示 wi,si 。

接下来 m 行,每行四个正整数,其中第 i 行表示 xi,yi,ci,di 。

第 n+m+2 行一个非负整数 Q 。

接下来 Q 行,每行三个正整数 x,a,b ,若 x≤n 则表示小Q把 wx 改为 a ,把 sx 改为 b ;若 n<x≤n+m 则表示小Q把 cx−n 改为 a ,把 dx−n 改为 b 。

输出格式

输出 Q+1 行,每行一个正整数,第 1 行表示所有修改之前的答案,第 i+1(1≤i≤Q) 行表示第 i 次修改之后的答案。

样例数据

样例输入

2 1
2 3
4 7
1 2 5 7
1
1 2 6

样例输出

16
18

样例解释

公园的线路图如图所示。

修改之前,最优方案为 1 号景点使用西部主题,2 号景点使用科幻主题,美观度之和为 2+7+7=16 。

修改之后,最优方案为 1 号景点使用科幻主题,2 号景点使用科幻主题,美观度之和为 6+7+5=18 。

样例输入

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

样例输出

72
71
70
68
71

子任务

保证 2≤n≤100000,Q≤100000;xi,yi≤n ,x≤n+m ,si,wi,ci,di,a,b≤106。保证线路图是小Q设计的。

按照常理,公园是有出入口的。但是在本题中,你可以认为公园的出入口也是景点。

定义环路为起点和终点相同,并且中间(即除起点终点外)不经过重复景点的路径上道路的集合。

  • 子任务 1(2 分):Q=0,m=n−1;
  • 子任务 2(3 分):n≤17,Q≤17;
  • 子任务 3(7 分):Q=0,每条道路最多属于一个环路;
  • 子任务 4(5 分):Q=0;
  • 子任务 5(13 分):n,Q≤1000;
  • 子任务 6(19 分):si=wi=0,x>n,每条道路最多属于一个环路;
  • 子任务 7(17 分):si=wi=0,x>n;
  • 子任务 8(23 分):m=n−1;
  • 子任务 9(11 分):无特殊限制。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2 1
2 3
4 7
1 2 5 7
1
1 2 6
16
18

样例 2

5 6
4 8
5 2
3 7
5 3
4 9
1 2 3 8
1 3 7 4
2 3 9 2
2 4 7 9
1 5 4 9
3 5 6 4
4
4 2 6
9 6 3
7 4 2
2 8 5
72
71
70
68
71