转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents    by---cxlove

题意：给出一个带边权的图。对于每一个询问(S , T , K , A , B)，有两种操作，加一条单位边花费为A，将某条边流量扩展一个单位花费为B，在预算为K的情况下求S到T最大流的最大值。

http://acm.hdu.edu.cn/showproblem.php?pid=4729

做法：如果A <= B，很明显只做添加边操作，而且只加在S - T之间，加一条边流量加1。所以结果是初始流量 + K / A。

如果A > B，则有两种可能，要进行添加边操作，这样的话，显然只添加一条边，就是S - T，然后 不断扩展这条边，那么结果就是初始流量 + K >= A ? 1 : 0 + max (0 , (K - A) / B)。

否则的话，便是只进行扩展操作。

第一个问题：怎么求出初始流量，显然是路径中边权最小的值，问题转化为树上第K大，主席树可以解决 。

第二个问题：只进行扩展操作。显然可以二分，然后判断路径中边权小于这个值的和，以及个数。就能算出花费。但是这样貌似会超时，可以直接在线段树进行逼近。差不多就是用线段树完成二分操作，算出可以增加到的最大限度。

第一次写的时候是按流量离散化了。。。。然后 发现在第二个问题是不方便实现。。。离散化之后不好统计。然后 发现流量只有1W，就直接建树了。。。连续情况下就考虑了所有情况。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <set>

#include <map>

#include <string>

#include <vector>

#include <queue>

#include <stack>

#define lowbit(x) (x & (-x))

#define Key_value ch[ch[root][1]][0]

#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

typedef long long LL;

const int N = 110005;

const int M = 2000000;

struct Edge {

    int v , w , next;

}edge[N << 1];

int n , q;

int start[N] , tot;

void _add (int u , int v , int w) {

    edge[tot].v = v;

    edge[tot].w = w;

    edge[tot].next = start[u];

    start[u] = tot ++;

}

void add (int u , int v , int w) {

    _add (u , v , w);

    _add (v , u , w);

}

int depth , b[N << 1] , cnt , p[N] , f[N];

int x[N] , m;

int T[M] , num[M] , sum[M] , nodecnt , lson[M] , rson[M];

void Init_hash () {

    sort (x , x + n - 1);

    m = unique (x , x + n - 1) - x;

}

int hash (int y) {

    return y;

    return lower_bound (x , x + m , y) - x + 1;

}

int bulid (int l , int r) {

    int root = nodecnt ++;

    num[root] = 0;

    sum[root] = 0;

    if (l != r) {

        int mid = (l + r) >> 1;

        lson[root] = bulid (l , mid);

        rson[root] = bulid (mid + 1 , r);

    }

    return root;

}

int update (int root , int l , int r , int pos , int val) {

    int newroot = nodecnt ++;

    num[newroot] = num[root] + 1;

    sum[newroot] = sum[root] + val;

    if (l != r) {

        int mid = (l + r) >> 1;

        if (pos <= mid) {

            lson[newroot] = update (lson[root] , l , mid , pos , val);

            rson[newroot] = rson[root];

        }

        else {

            rson[newroot] = update (rson[root] , mid + 1 , r , pos , val);

            lson[newroot] = lson[root];

        }

    }

    return newroot;

}

// search kth

int query (int left_root , int right_root , int lca_root , int l , int r , int k) {

    if (l == r) return l;

    int cal = num[lson[left_root]] + num[lson[right_root]] - 2 * num[lson[lca_root]];

    int mid = (l + r) >> 1;

    if (cal >= k)

        return query (lson[left_root] , lson[right_root] , lson[lca_root] , l , mid , k);

    else

        return query (rson[left_root] , rson[right_root] , rson[lca_root] , mid + 1 , r , k - cal);

}

int query (int left_root , int right_root , int lca_root , int k) {

    int calcnt = num[left_root] + num[right_root] - 2 * num[lca_root];

    int l = 1 , r = m;

    int nowcnt = 0 , nowsum = 0;

    while (l < r) {

        int tmpcnt = num[lson[left_root]] + num[lson[right_root]] - 2 * num[lson[lca_root]];

        int tmpsum = sum[lson[left_root]] + sum[lson[right_root]] - 2 * sum[lson[lca_root]];

        int mid = (l + r) >> 1;

        if (mid * (tmpcnt + nowcnt) - tmpsum - nowsum >= k) {

            r = mid;

            left_root = lson[left_root];right_root = lson[right_root];lca_root = lson[lca_root];

        }

        else {

            l = mid + 1;

            nowcnt += tmpcnt;nowsum += tmpsum;

            left_root = rson[left_root];right_root = rson[right_root];lca_root = rson[lca_root];

        }

    }

    if (k - (nowcnt * l - nowsum) < 0) l --;

    return l + (k - (nowcnt * l - nowsum)) / calcnt;

}

void dfs(int u , int pre){

    int t = ++ depth;

    b[++ cnt] = t;

    f[t] = u;

    p[u] = cnt;

    for(int i = start[u] ; i != -1 ; i = edge[i].next){

        int v = edge[i].v , w = edge[i].w;

        if (v == pre) continue;

        T[v] = update (T[u] , 1 , m , hash(w) , w);

        dfs (v , u);

        b[++ cnt] = t;

    }

}

int dp[N << 1][20];

void Init_rmq(int n){

    for(int i = 1 ; i <= n ; i++)

        dp[i][0] = b[i];

    int m = floor (log (n * 1.0) / log (2.0));

    for (int j = 1 ; j <= m ; j ++)

        for (int i = 1;i <= n - (1 << j) + 1 ; i ++)

            dp[i][j] = min (dp[i][j - 1] , dp[i + (1 << (j - 1))][j - 1]);

}

int rmq (int l , int r){

    int k = floor (log ((r - l + 1) * 1.0) / log (2.0));

    return min (dp[l][k] , dp[r - (1 << k) + 1][k]);

}

int lca (int a , int b){

    if (p[a] > p[b]) swap(a , b);

    return f[rmq (p[a] , p[b])];

}  

int main () {

    #ifndef ONLINE_JUDGE

        freopen ("input.txt" , "r" , stdin);

        // freopen ("output.txt" , "w" , stdout);

    #endif

    int t , cas = 0;

    scanf ("%d" , &t);

    while (t --) {

        tot = depth = cnt = nodecnt = 0;

        memset (start , -1 , sizeof(start));

        scanf ("%d %d" , &n , &q);

        for (int i = 1 ; i < n ; i ++) {

            int u , v , w;

            scanf ("%d %d %d" , &u , &v , &w);

            add (u , v , w + 1);

            x[i - 1] = w;

        }

        // Init_hash ();

        m = 10000;

        T[1] = bulid (1 , m);

        dfs (1 , 0);

        Init_rmq (cnt);

        printf ("Case #%d:\n" , ++cas);

        while (q --) {

            int s , e , k , a , b;

            scanf ("%d %d %d %d %d" , &s , &e , &k , &a , &b);

            int initial = query (T[s] , T[e] , T[lca (s , e)] , 1 , m , 1);

            if (a <= b) printf ("%d\n" , initial + k / a - 1);

            else {

                int ans = initial;

                if (k >= a) ans = ans + 1 + (k - a) / b;

                int ret = query (T[s] , T[e] , T[lca (s , e)] , k / b);

                // cout << initial << " " << ans << " " << ret << endl;

                printf ("%d\n" , max (ans , ret) - 1);

            }

        }

    }

    return 0;

}