传送门：HDU4729
【题意】给出一棵树，N结点，M个询问，每个询问(S,T,K,A,B)求出点S和T之间的最大流，可以新建或者扩展原路径上的流量，新建一个流量为1的边花费A，扩展流量1花费B，问最终的最大流；
【分析】首先(S,T)之间的初始流量st就是两点之间的最小边，因为是书，两点之间只有一条路径，用主席树每个点新建一棵树，配合上LCA即可用s+t-2*LCA(s,t)求出S-T的最小边st。
然后对于A<=B的情况，直接在S和T之间新建K/A条边肯定是最大流，则最大流为st+K/A
A>B的情况有两种方案：1.S-T新建一条边，然后在这条边上扩展(K-A)/B次，则最大流为st+(K<A?0:1+(K-A)/B)
2.不新建任何边，再原有边上扩展，本题难点就在这；在主席树上直接二分，判断当前1~mid中所包含的点数cnt以及前缀和s，如果k < cnt*mid-s则往左，否则往右，在叶子上时不能直接输出，还需要判断当前叶子是否能包含，以及是否能超过mx，所以k < cnt*mid-s时说明需要往前退，则是 x-1+(k-(cnt[x-1]*(x-1)-s[x-1]))/cnt[cnt-1];否则输出x+(k-(cnt*x-s))/cnt；
【AC CODE】499ms
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 100000+10, MAXM = MAXN*2, MAXV = 100000*30;
char buf[MAXN*5], *ps = buf, *pe = buf+1;
inline void rnext(){
if(++ps == pe)
pe = (ps = buf)+fread(buf,1,sizeof(buf),stdin);
}
inline int in()
{
int ans = 0;
do{
rnext();
}while(!isdigit(*ps) && ps != pe);
do
{
ans = (ans<<1)+(ans<<3)+*ps-48;
rnext();
}while(isdigit(*ps) && ps != pe);
return ans;
}
int head[MAXN], tol,nxt[MAXM],to[MAXM],cost[MAXM];
int rt[MAXN],c[MAXV],sum[MAXV], lc[MAXV], rc[MAXV],all,mx;
inline void add_edge(int u, int v, int c)
{
nxt[tol] = head[u], to[tol] = v, cost[tol] = c;
head[u] = tol++;
}
void insert(int &u, int x, int y, int v)
{
c[++all] = c[u]+1,sum[all] = sum[u]+v,lc[all] = lc[u],rc[all] = rc[u];
u = all;
if(x == y) return;
int m = (x+y)>>1;
if(v <= m) insert(lc[u],x,m,v);
else insert(rc[u],m+1,y,v);
}
/*LCA*/
int d[MAXN<<1], num[MAXN<<1],cnt,ft[MAXN],fa[MAXN];
void dfs(int u, int dep)
{
d[cnt] = dep,num[cnt] = u;ft[u] = cnt++;
for(int i = head[u]; ~i; i = nxt[i])
{
int v = to[i];
if(fa[u] == v) continue;
insert(rt[v]=rt[u],0,mx,cost[i]);
fa[v] = u;
dfs(v,dep+1);
d[cnt] = dep, num[cnt++] = u;
}
}
int mi[MAXN<<2],minum[MAXN<<2];
inline int id(int x, int y){return x+y|x!=y;}
void lca_bulid(int x, int y)
{
int u = id(x,y);
if(x == y)
{
mi[u] = d[x];
minum[u] = num[x];
return;
}
int m = (x+y)>>1;
lca_bulid(x,m);
lca_bulid(m+1,y);
int l = id(x,m), r = id(m+1,y);
if(mi[l] < mi[r]) mi[u] = mi[l],minum[u] = minum[l];
else mi[u] = mi[r], minum[u] = minum[r];
}
void init(int root)
{
all = cnt = 0;
fa[root] = -1;
rt[root] = rt[0];
dfs(root,0);
lca_bulid(0,cnt-1);
}
int qid,qmi;
void lca_q(int x, int y, int ql, int qr)
{
if(ql <= x && y <= qr)
{
int u = id(x,y);
if(qmi > mi[u])
qmi = mi[u], qid = minum[u];
return;
}
int m = (x+y)>>1;
if(ql <= m) lca_q(x,m,ql,qr);
if(qr > m) lca_q(m+1,y,ql,qr);
}
int lca_query(int x, int y)
{
x = ft[x], y = ft[y];
if(x > y) swap(x,y);
qmi = INF;
lca_q(0,cnt-1,x,y);
return qid;
}
int mi_query(int x, int y, int a, int b, int lca)
{
if(x == y) return x;
int m = (x+y)>>1;
int cnt = c[lc[a]]+c[lc[b]]-2*c[lc[lca]];
if(cnt) return mi_query(x,m,lc[a],lc[b],lc[lca]);
return mi_query(m+1,y,rc[a],rc[b],rc[lca]);
}
int find(int x, int y, int a, int b, int lca, int k, int lcnt, int lsum)
{
if(x == y)
{
int cnt = c[a]+c[b]-2*c[lca]+lcnt, s = sum[a]+sum[b]-2*sum[lca]+lsum;
if(k < cnt*x-s)
return x-1+(k-(lcnt*(x-1)-lsum))/lcnt;
return x+(k-(cnt*x-s))/cnt;
}
int m = (x+y)>>1;
int cnt = c[lc[a]]+c[lc[b]]-2*c[lc[lca]]+lcnt, s = sum[lc[a]]+sum[lc[b]]-2*sum[lc[lca]]+lsum;
if(k < cnt*m-s) return find(x,m,lc[a],lc[b],lc[lca],k,lcnt,lsum);
return find(m+1,y,rc[a],rc[b],rc[lca],k,cnt,s);
}
int query(int s, int t, int k, int a, int b)
{
int lca = lca_query(s,t);
int st = mi_query(0,mx,rt[s],rt[t],rt[lca]);
if(a <= b)
return st+k/a;
int ans = st+((k<a)?0:(1+(k-a)/b));
ans = max(ans,find(0,mx,rt[s],rt[t],rt[lca],k/b,0,0));
return ans;
}
int main()
{
#ifdef SHY
freopen("d:\\1.txt", "r", stdin);
#endif
int t = in(),count = 0;
while(t--)
{
int n = in(),q = in();
clc(head,-1);
tol = mx = 0;
rep(i,1,n)
{
int u = in(),v = in(),c = in();
mx = max(mx,c);
add_edge(u,v,c);
add_edge(v,u,c);
}
init(1);
printf("Case #%d:\n",++count);
while(q--)
{
int s = in(),t = in(),k = in(),a = in(),b = in();
printf("%d\n", query(s,t,k,a,b));
}
}
return 0;
}
