Brief description:
。。。 n 个结点的带容量无向树，m 个询问。
每个询问形如 (s, t, k, a, b)。。表示。。
。。允许已 a 的代价修建一条单位容量的新边，b 的代价将一条旧边或新边增加单位流量。。
。。预算为 k 时 s->t 的最大流。。
Analysis:
。。先考虑加边的情况。。如果要加边的话。。只会加在 s->t 上。。。
。。如果a <= b 。。那么狂加边就行了。。。否则的话。。只会添加一条边。。且扩容操作全部给这条边最优。
。。接下来考虑不加边的情况。。取出 s->t 路径上的所有边权。。在预算范围内尽可能让红线画的更高。。推更多的流。。。。显然这是树上区间 kth 问题。。。可以使用主席树。。。。
本来主席树求 kth 大是只带一个 logn 的。。。我比赛的时候搞着搞着又搞成二分那条红线了。又把第二个 logn 加回来艹。。。
。。。。
。。言归正传。。。对于求 s->t 的初始 flow 的过程。。就是求这个路径上 rmq。。。
。。现在反正有了主席树那么求初始流可以用 kth() 。。解决。（这里 k 固定为 1）。。。
。。在预算范围至多还能推多少流的函数我们记作 kth2() 。。这里的 "k" 表示预算。。在这个函数的末尾。。求出流量后我们立刻返回收益。。
。。（注意。。主席树的值域我们只开到 10000.。 所以可能返回收益的时刻还有没有花完的预算。。还可以继续加上。。
。。。。需要维护。。。
。c[]：个数。。以及
。d[]：和。。
const int N = 100009, M = 2 * N, LM = 18;
int hd[N], suc[M], to[M], wt[N];
int ST[LM][M], st[N], dep[N]; // Euler index ...
int n, tt; int T[N], Null;
const int NN = 20 * N;
int l[NN], r[NN], c[NN], d[NN], total;
// Chairman tree
#define lx l[x]
#define rx r[x]
#define ly l[y]
#define ry r[y]
#define cx c[x]
#define cy c[y]
#define ml (ll+rr>>1)
#define mr (ml+1)
#define lc lx, ll, ml
#define rc rx, mr, rr
#define lt lx = ++total, rx = ry, x = lx, y = ly, rr = ml
#define rt lx = ly, rx = ++total, x = rx, y = ry, ll = mr
int Tn;
int new_node(){
++total; l[total] = r[total] = c[total] = d[total] = 0;
return total;
}
int Insert(int y, int p){
int x = new_node(), root = x, ll = 0, rr = Tn;
c[x] = c[y] + 1, d[x] = d[y] + p;
while (ll < rr){
if (p < mr) lt; else rt;
c[x] = c[y] + 1, d[x] = d[y] + p;
}
return root;
}
inline bool elder(int a, int b){
return dep[a] < dep[b];
}
inline int lca(int a, int b){
int l = st[a], r = st[b];
if (l > r) swap(l, r); ++r; int lv = lg2(r-l); //log2(r - l);
return min(ST[lv][l], ST[lv][r-(1<<lv)], elder);
}
#define aa to[i^1]
#define bb to[i]
#define v bb
#define ww wt[i/2]
void dfs(int u = 1){
ST[0][st[u] = ++tt] = u;
REP_G(i, u) if (!st[v]){
dep[v] = dep[u] + 1, T[v] = Insert(T[u], ww);
dfs(v);
ST[0][++tt] = u;
}
}
int kth2(int x, int y, int k){
int z = lca(x, y);
x = T[x], y = T[y], z = T[z];
int ll = 0, rr = Tn, t, cc = 0, dd = 0;
int D = c[x] + c[y] - 2*c[z], tc, td;
while (ll < rr){
if (ml * (cc + (tc = c[lx] + c[ly] - 2*c[l[z]])) - (dd + (td = d[lx] + d[ly] - 2*d[l[z]])) >= k){
x = l[x], y = l[y], z = l[z];
rr = ml;
}
else {
x = r[x], y = r[y], z = r[z];
cc += tc, dd += td, ll = mr;
}
}
if ((k-((cc*ll)-dd))<0) --ll;
return ll + (k-((cc*ll)-dd))/D;
}
int kth(int x, int y, int k){
int z = lca(x, y);
x = T[x], y = T[y], z = T[z];
int ll = 0, rr = Tn, t;
while (ll < rr){
if ((t = c[l[x]] + c[l[y]] - 2*c[l[z]]) >= k){
x = l[x], y = l[y], z = l[z];
rr = ml;
}
else {
x = r[x], y = r[y], z = r[z];
k -= t, ll = mr;
}
}
return ll;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out2.txt", "w", stdout);
#endif
Rush{
printf("Case #%d:\n", ++Case);
int Q; RD(n, Q); fill(hd+1, hd+n+1, 0); fill(st+1, st+n+1, 0);
Tn = 0; FOR_C(i, 2, n << 1){
RD(to[i], to[i|1]); checkMax(Tn, RD(ww));
suc[i] = hd[aa], hd[aa] = i++;
suc[i] = hd[aa], hd[aa] = i;
}
total = 0, T[1] = new_node();
tt = 0, dfs();
for ( int lv = 1 ; _1(lv) <= tt ; lv ++ ){
for ( int i = 1 ; i + _1(lv) <= tt + 1 ; i ++ )
ST[lv][i] = min(ST[lv-1][i], ST[lv-1][i + _1(lv-1)], elder);
}
DO(Q){
int s, t, k, a, b; RD(s, t, k, a, b);
int flow = kth(s, t, 1), res = a <= b ? k/a + flow : max((k>=a?(k-a)/b+1:0) + flow, kth2(s, t, k/b));
printf("%d\n", res);
}
}
}
External link:
https://gist.github.com/lychees/6562208
https://www.shuizilong.com/house/archives/spoj-10628-count-on-a-tree/
