物流运输 CH Round #45 - alan有一些陷阱 III

题目描述

    随着网购在H国兴起，其物流业也随之开始发展。

    H国可共有$N$座城市，由$1 \sim N$编号，物流公司的总部设在1号城市。

    城市之间由$N-1$条单向主干道连接。从物流公司总部所在的城市出发，总能经过唯一的一条仅包含主干道的道路，到达其余$N-1$座城市。除此之外，城市间还有$M$条单向次干道。所有的道路间都不会构成环。

    为了减缓道路的压力，每单位货物经过道路$i$都会被收取$V_{i}$的费用。

    另外，每条道路还有一个额定运载量$W_{i}$。如果该条道路运输的货物少于$W_{i}$，则每少一单位货物要多被收取$P_{i}$的费用；如果该条道路运输的货物多于$W_{i}$，则每多一单位要多被收取$Q_{i}$的费用。

    随着环境的变化，主干道的额定运载量会随之发生一些变化。你的任务是帮助物流公司预算每一次运输的成本。

    你需要实现两种操作：

    (1)$C~x~y~k$，表示将城市$x$和城市$y$之间的主干道的额定运载量增加$k$。

    (2)$Q~x~d$，表示询问将$d$单位的货物从物流公司总部运输到城市$x$花费的最小费用。

    注：如果某条边的额定运载量$W_{i}<0$，我们在运输货物时认为它的额定运载量为0，但实际的$W_{i}$值不变。

输入格式

    第一行2个整数$N$和$M$。

    接下来$N-1$行，描述$N-1$条主干道，每行6个整数$u,v,W_{i},V_{i},P_{i},Q_{i}$。其中$u,v$表示城市$u$到$v$有一条单向道路。

    接下来$M$行，描述$M$条次干道，格式同上。

    接下来一个整数$T$，表示有$T$次操作。

    接下来$T$行，每行表示一个操作，格式见题目描述。

输出格式

    对于每一次类型(2)的询问，输出最小费用。

样例输入

6 1
1 2 2 2 2 2
1 3 3 3 2 2
2 4 2 2 1 2
2 5 3 1 2 3
5 6 3 3 2 1
3 6 2 1 1 1
3
Q 6 6
C 6 2 -1
Q 6 6

样例输出

35
34

数据范围与约定

  • 对于100%的数据：$0 \leq W_{i} \leq 1000,0 \leq V_{i},P_{i},Q_{i} \leq 20,|k| \leq 100,0 \leq d \leq 1000$。
  • 保证类型(2)的询问不会很多，计算过程和最终结果都不会超过maxlongint。