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/

Posted by xiaodao
Category: HDU