HDU 4729. An Easy Problem for Elfness

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
http://www.shuizilong.com/house/archives/spoj-10628-count-on-a-tree/