以根为原点，所有叶子为汇点建立网络。
对于一条边$(x,y,A,B)$，$x$向$y$连边，容量$A$，费用0，再连边，容量$B-A$，费用1。
然后不断增广，直到费用达到$M$为止的最大流即为答案。
考虑用树链剖分+线段树来模拟这个过程：
首先加入所有费用为0的边，每次求出到根距离最小的可增广的叶子，然后求出路径上容量的最小值，将所有边的容量减掉它。
如果减的过程中有边容量变为0，那么将它加入临时数组$q$中。
然后扫描$q$中所有边，如果一条边之前费用为0，那么把它容量设置为$B-A$，然后将子树内费用都加一，否则将它子树内的点都标记为不可增广。
时间复杂度$O(nlog^2n)$。
#include<cstdio>
const int N=10010,M=33000,inf=~0U>>1;
int n,m,i,x,y,A,B,ans,cnt,q[N],mf[M],mc[M],tf[M],tc[M],td[M];
int g[N],v[N],nxt[N],f[N],d[N],wa[N],wb[N],size[N],son[N],top[N],st[N],en[N],dfn,seq[N],S[N];
void dfs(int x){
size[x]=1;son[x]=-1;
for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]){
d[v[i]]=d[x]+1;dfs(v[i]);size[x]+=size[v[i]];
if(son[x]<0||size[v[i]]>size[son[x]])son[x]=v[i];
}
}
void dfs2(int x,int y){
seq[st[x]=++dfn]=x;top[x]=y;
if(~son[x])dfs2(son[x],y);
for(int i=g[x];i;i=nxt[i])if(v[i]!=son[x]&&v[i]!=f[x])dfs2(v[i],v[i]);
en[x]=dfn;
}
inline int min(int a,int b){return a<b?a:b;}
inline void tagf(int x,int y){mf[x]-=y;tf[x]+=y;}
inline void tagc(int x,int y){if(mc[x]<inf)mc[x]+=y;tc[x]+=y;}
inline void tagd(int x){mc[x]=inf;tc[x]=0;td[x]=1;}
inline void pb(int x){
if(tf[x])tagf(x<<1,tf[x]),tagf(x<<1|1,tf[x]),tf[x]=0;
if(tc[x])tagc(x<<1,tc[x]),tagc(x<<1|1,tc[x]),tc[x]=0;
if(td[x])tagd(x<<1),tagd(x<<1|1),td[x]=0;
}
inline void up(int x){
mf[x]=min(mf[x<<1],mf[x<<1|1]);
mc[x]=min(mc[x<<1],mc[x<<1|1]);
}
void build(int x,int a,int b){
if(a==b){
int y=seq[a];
mf[x]=wa[y];
if(size[y]>1)mc[x]=inf;
return;
}
int mid=(a+b)>>1;
build(x<<1,a,mid),build(x<<1|1,mid+1,b),up(x);
}
void modifyf(int x,int a,int b,int c,int p){
if(a==b){mf[x]=p;return;}
pb(x);
int mid=(a+b)>>1;
if(c<=mid)modifyf(x<<1,a,mid,c,p);else modifyf(x<<1|1,mid+1,b,c,p);
up(x);
}
void changef(int x,int a,int b,int c,int d,int p){
if(c<=a&&b<=d&&mf[x]>p){tagf(x,p);return;}
if(a==b){
q[++cnt]=seq[a];
mf[x]=0;
return;
}
pb(x);
int mid=(a+b)>>1;
if(c<=mid)changef(x<<1,a,mid,c,d,p);
if(d>mid)changef(x<<1|1,mid+1,b,c,d,p);
up(x);
}
void changec(int x,int a,int b,int c,int d){
if(c<=a&&b<=d){tagc(x,1);return;}
pb(x);
int mid=(a+b)>>1;
if(c<=mid)changec(x<<1,a,mid,c,d);
if(d>mid)changec(x<<1|1,mid+1,b,c,d);
up(x);
}
void changed(int x,int a,int b,int c,int d){
if(c<=a&&b<=d){tagd(x);return;}
pb(x);
int mid=(a+b)>>1;
if(c<=mid)changed(x<<1,a,mid,c,d);
if(d>mid)changed(x<<1|1,mid+1,b,c,d);
up(x);
}
int askmf(int x,int a,int b,int c,int d){
if(c<=a&&b<=d)return mf[x];
pb(x);
int mid=(a+b)>>1,t=inf;
if(c<=mid)t=askmf(x<<1,a,mid,c,d);
if(d>mid)t=min(t,askmf(x<<1|1,mid+1,b,c,d));
return up(x),t;
}
inline int getmc(){
int x=1,a=2,b=dfn,mid;
while(a<b){
mid=(a+b)>>1;
if(mc[x<<1]<mc[x<<1|1])x<<=1,b=mid;else x=x<<1|1,a=mid+1;
}
return seq[a];
}
inline int getmf(int x){
int t=inf;
while(top[x])t=min(t,askmf(1,2,dfn,st[top[x]],st[x])),x=f[top[x]];
if(st[x]>=2)t=min(t,askmf(1,2,dfn,2,st[x]));
return t;
}
inline void chain(int x,int y){
cnt=0;
while(top[x])changef(1,2,dfn,st[top[x]],st[x],y),x=f[top[x]];
if(st[x]>=2)changef(1,2,dfn,2,st[x],y);
while(cnt){
x=q[cnt--];
if(!S[x]&&wb[x]>wa[x])modifyf(1,2,dfn,st[x],wb[x]-wa[x]),changec(1,2,dfn,st[x],en[x]);
else changed(1,2,dfn,st[x],en[x]);
S[x]++;
}
}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d%d%d%d",&x,&y,&A,&B);
v[i]=y,nxt[i]=g[x],g[x]=i;
f[y]=x,wa[y]=A,wb[y]=B;
}
dfs(0),dfs2(0,0),build(1,2,dfn);
while(mc[1]<inf){
y=getmf(x=getmc());
if(mc[1]*y>m)y=m/mc[1];
if(!y)break;
m-=mc[1]*y;
ans+=y;
chain(x,y);
}
return printf("%d",ans),0;
}