简要题意：给一颗\(n\)个点的二叉树，
par[i]=i/2，每个点有\(a[i]\)个果实，有\(m\)次操作，每次在\(u\to v\)（保证\(u\)是\(v\)的祖先）中取不超过\(c\)个果实，每取一个贡献\(w\)的收益
首先可以暴力建边然后费用流。考虑优化，有一种显然的贪心策略：按照\(w\)从大到小依次尽量选最多，判断可以二分加二分图匹配。
考虑霍尔定理，相当于对于任意子集的并，\(\sum _{i \in S} a[i] \ge \sum _{u_i\in S \& v_i\in S} c_i\)。
显然我们只需要考虑这个并是一个联通块的情况。考虑\(dp\)出以\(i\)为根的最小子树。
因为确定了根，我们可以把\(c_i\)赋值到\(v_i\)上。
转移是
\[
f[i][j] = \min (f[i*2][j],0)+\min (f[i*2+1][j],0-0) + val[i][j]
\]
预处理\(n\log n\)，插入一条链以及算包含一条链的最小联通块复杂度\(n\log ^2n\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
typedef long long ll;
long long f[20][N<<1],g[20][N<<1];
int dep[N],a[N];
int n,m;
ll ans=0;
struct Line{
int u,v,cap,w;
bool operator < (const Line b)const{return w < b.w;}
void read(){scanf("%d%d%d%d",&u,&v,&cap,&w);}
}l[N];
void Main(){
ans=0;
cin >> n >> m;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
dep[i]=dep[i>>1]+1;
for(int j=dep[i];j;j--)g[j][i]=a[i];
}
for(int i=1;i<=dep[n];i++){
for(int j=n;j;j--)f[i][j]=min(0ll,f[i][j<<1|1])+min(0ll,f[i][j<<1])+g[i][j];
}
for(int i=1;i<=m;i++)l[i].read();
sort(l+1,l+m+1);
for(int i=m;i;i--){
int hed=l[i].u;ll Mn=l[i].cap;
for(;hed;hed>>=1){
int d=dep[hed],nxt=l[i].v,lst=0;ll ths=0;
while(nxt!=(hed>>1)){
ths+=min(0ll,(nxt<<1|1)==lst?0ll:f[d][nxt<<1|1])+min(0ll,(nxt<<1)==lst?0ll:f[d][nxt<<1])+g[d][nxt];
lst=nxt;nxt>>=1;
}
Mn=min(Mn, ths);
}
ans+=l[i].w*Mn;
hed=l[i].u;
for(;hed;hed>>=1){
int nxt=l[i].v,d=dep[hed];
g[d][nxt]-=Mn;
for(;nxt;nxt>>=1){
f[d][nxt]=min(0ll,f[d][nxt<<1])+min(0ll,f[d][nxt<<1|1])+g[d][nxt];
}
}
}
for(int d=1;d<=dep[n];d++)for(int i=1;i<=n;i++)f[d][i]=g[d][i]=0;
cout << ans << endl;
}
int main()
{
int T;cin >> T;
while(T--){
Main();
}
return 0;
}