Problem Description
瑶瑶（tsyao）是某知名货运公司（顺丰
）的老板，这个公司很大，货物运输量极大，因此公司修建了许多交通设施，掌控了一个国家的交通运输。
这个国家有n座城市，公司的总部在1号城市。
公司下管辖的有m条道路和n-1段火车线路。
这m条道路和n-1条火车线路都可以用u来表示起点，v来表示终点（数据保证m条道路和n-1条火车线路构成有向无环图）。
这n-1段火车道保证从1号城市出发，能够有唯一的一道只包含火车道的线路到达其他n-1座城市。
每条道路和每段火车道都有一个最佳搭载货物值ai，如果要搭载的货物超过了ai，公司需要对经过该路线的超过ai的每单位货物增加bi的维修费用，由于种种原因，如果搭载的货物低于ai，公司需要对少的每单位货物(设该路线有x的货物，则计算为ai-x单位)增加ci的维修费用。当然，每单位货物经过时，会有di的基础维护费用。
这里有两种操作：
C xi yi zi： 随着时间和环境的变化，火车道会受到一些影响，xi到yi的火车道ai会改变zi(新的ai应该为ai+zi)，若xi不能到达yi，则将hi到xi和hi到yi的路段ai改变zi(hi为可以到达xi和yi的城市，且不存在fi使得 hi能够到达fi，fi能够到达xi和yi)。
当某火车道的ai值小于0时，我们看做该条火车道的最佳搭载货物值为0(当然ai事实上是负数)；
Q vi wi： 查询当计划将wi单位货物从1号城市到vi号城市时，该公司需要的最小维护费用。维护费用计算为每条道路和火车道的维护费用的和(SUMbi+SUMci+SUMdi)。
Input
第一行两个整数n，m，用空格隔开。
接下来n-1+m行，每行u，v，ai，bi，ci，di六个整数。
前n-1行表示火车线路，后m行表示道路。
接下来一行为一个整数q。
接下来q行分别为上述两种操作。
Output
对于每次Q操作，输出答案，数据保证答案在int范围内。
题目大意：略。
思路：
——————————————————————————————————————————————————————————————————
扒官方题解：http://tsyao.tk/archives/94
对付修改的话，就用树链剖分就好，然后每次询问跑网络流。
网络流这样建图，先假设我每条边都跑了0的流量，我们先算出跑了0的流量的费用，然后对于一条边，我跑了小于ai的流量的时候，每次增加一点流量，就相当于减小了ci的费用，所以把一条边拆成两条边，一条是费用为-ci+di，上界为ai的边，一条是费用为bi+di，上界为无穷的边。。。
——————————————————————————————————————————————————————————————————
PS：简单的说就是两条SB题合在一起出，这样也脱离不了它是SB题的结果。但是却忘了删一条调试语句导致无限TLE……
代码（1772MS）：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long LL; const int MAXN = ;
const int MAXV = MAXN;
const int MAXE = * ( * + MAXN * );
const int MAXT = MAXN << ;
const int INF = 0x3f3f3f3f; struct SPFA_COST_FLOW {
int head[MAXV];
int to[MAXE], next[MAXE], cap[MAXE], flow[MAXE];
LL cost[MAXE];
int n, m, ecnt, st, ed; void init(int n) {
this->n = n;
memset(head + , -, n * sizeof(int));
ecnt = ;
} void add_edge(int u, int v, int f, LL c) {
to[ecnt] = v; cap[ecnt] = f; cost[ecnt] = c; next[ecnt] = head[u]; head[u] = ecnt++;
to[ecnt] = u; cap[ecnt] = ; cost[ecnt] = -c; next[ecnt] = head[v]; head[v] = ecnt++;
} void clear() {
memset(flow, , ecnt * sizeof(int));
} LL dis[MAXV];
int pre[MAXV];
bool vis[MAXV]; bool spfa() {
memset(vis + , , n * sizeof(bool));
memset(dis, 0x3f, (n + ) * sizeof(LL));
queue<int> que; que.push(st);
dis[st] = ;
while(!que.empty()) {
int u = que.front(); que.pop();
vis[u] = false;
for(int p = head[u]; ~p; p = next[p]) {
int v = to[p];
if(cap[p] - flow[p] && dis[u] + cost[p] < dis[v]) {
dis[v] = dis[u] + cost[p];
pre[v] = p;
if(!vis[v]) {
que.push(v);
vis[v] = true;
}
}
}
}
return dis[ed] < dis[];
} LL maxFlow, minCost; LL min_cost_flow(int ss, int tt) {
st = ss, ed = tt;
maxFlow = minCost = ;
while(spfa()) {
int u = ed, tmp = INF;
while(u != st) {
tmp = min(tmp, cap[pre[u]] - flow[pre[u]]);
u = to[pre[u] ^ ];
}
u = ed;
while(u != st) {
flow[pre[u]] += tmp;
flow[pre[u] ^ ] -= tmp;
u = to[pre[u] ^ ];
}
maxFlow += tmp;
minCost += tmp * dis[ed];
}
return minCost;
}
} G; struct Tree {
struct Edge {
int a, b, c, d, u, v;
void read() {
scanf("%d%d%d%d%d%d", &u, &v, &a, &b, &c, &d);
}
} tree[MAXN], edge[MAXE];
int tid[MAXN], eid[MAXN], size[MAXN], son[MAXN], top[MAXN], dep[MAXN], fa[MAXN];
int n, m, q; int head[MAXV], pre[MAXV], ecnt, dfs_clock;
int to[MAXE], next[MAXE], id[MAXE];
LL add[MAXT]; void init() {
memset(head + , -, n * sizeof(int));
ecnt = dfs_clock = ;
} void add_edge(int u, int v, int i) {
to[ecnt] = v; id[ecnt] = i; next[ecnt] = head[u]; head[u] = ecnt++;
to[ecnt] = u; id[ecnt] = i; next[ecnt] = head[v]; head[v] = ecnt++;
} void dfs_size(int u, int f, int depth) {
size[u] = ; dep[u] = depth; fa[u] = f;
int maxsize = son[u] = ;
for(int p = head[u]; ~p; p = next[p]) {
int v = to[p];
if(v == f) continue;
pre[v] = p;
dfs_size(v, u, depth + );
size[u] += size[v];
if(size[v] > maxsize) {
maxsize = size[v];
son[u] = v;
}
}
} void dfs_heavy_edge(int u, int ancestor) {
tid[u] = ++dfs_clock; eid[dfs_clock] = id[pre[u]];
top[u] = ancestor;
if(son[u]) dfs_heavy_edge(son[u], ancestor);
for(int p = head[u]; ~p; p = next[p]) {
int v = to[p];
if(v == fa[u] || v == son[u]) continue;
dfs_heavy_edge(v, v);
}
} #define ll (x << 1)
#define rr (ll | 1)
#define mid ((l + r) >> 1) void pushdown(int x) {
if(add[x]) {
add[ll] += add[x];
add[rr] += add[x];
add[x] = ;
}
} void pushadd(int x, int l, int r) {
if(l == r) {
if(l > ) tree[eid[l]].a += add[x];
add[x] = ;
} else {
pushdown(x);
pushadd(ll, l, mid);
pushadd(rr, mid + , r);
}
} void modify(int x, int l, int r, int a, int b, int val) {
if(a <= l && r <= b) {
add[x] += val;
} else {
if(a <= mid) modify(ll, l, mid, a, b, val);
if(mid < b) modify(rr, mid + , r, a, b, val);
}
} void modify(int x, int y, int val) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
modify(, , n, tid[top[x]], tid[x], val);
x = fa[top[x]];
}
if(x != y) {
if(dep[x] < dep[y]) swap(x, y);
modify(, , n, tid[son[y]], tid[x], val);
}
} int gid[MAXV];
void initQuery() {
G.init(n + );
for(int i = ; i < n; ++i) {
Edge &t = tree[i];
gid[i] = G.ecnt;
G.add_edge(t.u, t.v, max(, t.a), t.d - t.c);
G.add_edge(t.u, t.v, INF, t.d + t.b);
}
for(int i = ; i < m; ++i) {
Edge &t = edge[i];
G.add_edge(t.u, t.v, max(, t.a), t.d - t.c);
G.add_edge(t.u, t.v, INF, t.d + t.b);
}
G.add_edge(n + , , , );
} int query(int tt, int val) {
int ss = n + ;
pushadd(, , n);
LL sum = ;
for(int i = ; i < n; ++i) {
Edge &t = tree[i];
sum += t.c * max(, t.a);
G.cap[gid[i]] = max(, t.a);
}
for(int i = ; i < m; ++i) {
Edge &t = edge[i];
sum += t.c * max(, t.a);
}
G.cap[G.ecnt - ] = val;
G.clear();
return sum + G.min_cost_flow(ss, tt);
} void work() {
scanf("%d%d", &n, &m);
for(int i = ; i < n; ++i) tree[i].read();
for(int i = ; i < m; ++i) edge[i].read();
init();
initQuery();
for(int i = ; i < n; ++i) add_edge(tree[i].u, tree[i].v, i);
dfs_size(, , );
dfs_heavy_edge(, );
scanf("%d", &q);
char op;
for(int i = , a, b, c; i < q; ++i) {
scanf(" %c", &op);
if(op == 'Q') {
scanf("%d%d", &a, &b);
printf("%d\n", query(a, b));
} else {
scanf("%d%d%d", &a, &b, &c);
modify(a, b, c);
}
}
}
} T; int main() {
T.work();
}