题意：
给出一棵树，每条边有一个容量。
有若干次询问：(S \, T \, K \, A \, B)，求路径(S o T)的最大流量。
有两种方法可以增大流量：
- 花费(A)可以新修一条管道，管道可以连接任意两个点，两个点之间可以有任意条管道连接，新修的管道容量为(1)
- 花费(B)可以使某条管道(包括新修的管道)的容量增加(1)
求在不超过预算(K)的情况下的最大流量。
分析：
注意到流量最大只有(10^4)，所以我们可以直接在值域上建一棵主席树。
主席树区间维护的是管道的个数以及它们的容量之和，这样方便后面的计算。
首先我们可以求一下路径上的第(1)小的容量，这是初始容量。
按照(A, B)的大小关系，有两种情况：
- (A leq B)，把所有的经费都用来修建新管道上。因为扩容一次不一定能使流量增加，但是新修管道一定可以增加流量，而且还便宜。
- (A > B)，这样就不能随便新建管道了，所以有两种可能：
- 只新建一条管道，然后再这条新管道上扩容
- 只在原来的管道上扩容
在求能扩容得到的最大容量可以用二分的思想，往主席树的左右子树走下去。
另：根据题面的数据范围，最终答案可能会爆int的，但是事实证明测试数据中没有这样的数据。。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 10;
const int M = 20;
int n, m;
struct Edge
{
int v, w, nxt;
Edge() {}
Edge(int v, int w, int nxt): v(v), w(w), nxt(nxt) {}
};
int ecnt, head[maxn];
Edge edges[maxn * 2];
void AddEdge(int u, int v, int w) {
edges[ecnt] = Edge(v, w, head[u]);
head[u] = ecnt++;
}
struct Node
{
int lch, rch, cnt, sum;
}T[maxn << 5];
int sz, root[maxn];
int update(int pre, int L, int R, int pos) {
int rt = ++sz;
T[rt] = T[pre];
T[rt].cnt++;
T[rt].sum += pos;
if(L < R) {
int M = (L + R) / 2;
if(pos <= M) T[rt].lch = update(T[pre].lch, L, M, pos);
else T[rt].rch = update(T[pre].rch, M+1, R, pos);
}
return rt;
}
int query(int u, int v, int l, int L, int R, int k) {
if(L == R) return L;
int M = (L + R) / 2;
int sum = T[T[u].lch].cnt + T[T[v].lch].cnt - T[T[l].lch].cnt * 2;
if(sum >= k) return query(T[u].lch, T[v].lch, T[l].lch, L, M, k);
else return query(T[u].rch, T[v].rch, T[l].rch, M+1, R, k - sum);
}
int fa[maxn], dep[maxn];
void dfs(int u) {
for(int i = head[u]; ~i; i = edges[i].nxt) {
int v = edges[i].v;
if(v == fa[u]) continue;
fa[v] = u;
dep[v] = dep[u] + 1;
root[v] = update(root[u], 0, M, edges[i].w);
dfs(v);
}
}
int anc[maxn][20];
void preprocess() {
memset(anc, 0, sizeof(anc));
for(int i = 1; i <= n; i++) anc[i][0] = fa[i];
for(int j = 1; (1 << j) < n; j++)
for(int i = 1; i <= n; i++) if(anc[i][j-1])
anc[i][j] = anc[anc[i][j-1]][j-1];
}
int LCA(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
int log;
for(log = 0; (1 << log) < dep[u]; log++);
for(int i = log; i >= 0; i--)
if(dep[u] - (1<<i) >= dep[v]) u = anc[u][i];
if(u == v) return u;
for(int i = log; i >= 0; i--)
if(anc[u][i] && anc[u][i] != anc[v][i])
u = anc[u][i], v = anc[v][i];
return fa[u];
}
int bsearch(int u, int v, int l, int x) {
int L = 0, R = M, cnt = 0, sum = 0;
while(L < R) {
int mid = (L + R) / 2;
int tcnt = T[T[u].lch].cnt + T[T[v].lch].cnt - T[T[l].lch].cnt * 2;
int tsum = T[T[u].lch].sum + T[T[v].lch].sum - T[T[l].lch].sum * 2;
if((cnt + tcnt) * mid - tsum - sum > x) {
u = T[u].lch, v = T[v].lch, l = T[l].lch;
R = mid;
} else {
cnt += tcnt; sum += tsum;
u = T[u].rch, v = T[v].rch, l = T[l].rch;
L = mid + 1;
}
}
return L - 1;
}
int main()
{
int _; scanf("%d", &_);
for(int kase = 1; kase <= _; kase++) {
printf("Case #%d:
", kase);
scanf("%d%d", &n, &m); sz = 0;
ecnt = 0;
memset(head, -1, sizeof(head));
for(int i = 1; i < n; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
AddEdge(u, v, w); AddEdge(v, u, w);
}
dfs(1); preprocess();
while(m--) {
int u, v, k, a, b;
scanf("%d%d%d%d%d", &u, &v, &k, &a, &b);
int lca = LCA(u, v);
int base = query(root[u], root[v], root[lca], 0, M, 1);
if(a <= b) printf("%d
", base + k / a);
else {
int ans = base;
if(k >= a) ans += (k - a) / b + 1;
int x = k / b;
ans = max(ans, bsearch(root[u], root[v], root[lca], x));
printf("%d
", ans);
}
}
}
return 0;
}