#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l,i##end=r;i<i##end;++i)
#define Rs(i,l,r) for(int i=l,i##end=r;i>i##end;--i)
#define Le(i,l,r) for(int i=l,i##end=r;i<=i##end;++i)
#define Re(i,l,r) for(int i=l,i##end=r;i>=i##end;--i)
#define L(i,l) for(int i=0,i##end=l;i<i##end;++i)
#define E(i,l) for(int i=1,i##end=l;i<=i##end;++i)
#define W(t) while(t--)
#define Wh while

const int N=25,M=2*N,inf=1e9,K=100010;
int n,h[N],e[M],ne[M],idx,b[K],c[K],res=inf,t[N][N],te[1<<20];
ll a[K];
// int path[N]{0,1};//don't forget memset h!
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int calc(ll x,ll a,ll b,ll c){
	// cout<<x<<' '<<a<<' '<<b<<' '<<c<<'\n';
	/*
	head:b+cx
	c>=0 b+cx,b+c(x+1),b+c(x+2),...,b+c*mid,等差数列求和即可
	c<0 b+tc>0     tc > -b    t < -b/c(ceil)
	
	she t=-b/c
		day < t    等差数列求和即可
		day>=t 前t-1项+(day-(t-1))
	*/
	ll head=b+c*x;
	if(head<1)return x+a-1;
	ll t=c<0?(b+(-c-1))/-c:-1,l=x,r=inf;
	__int128 fr=((__int128)t-x)*(head+b+c*(t-1))>>1;
	if(~t&&fr<=a)
		return t-1+a-fr;
	ll front=fr;
	Wh(l<r){
		__int128 mid=l+r>>1,res;
		if(c>=0||mid<t)res=(mid-x+1)*(b+b+c*(x+mid))>>1;
		else res=front+mid-t+1;
		if(res>=a)r=mid;
		else l=mid+1;
	}
	return r;
}
bool st[N]{0,1};
void dfs(int d,int st,int bj,int ans){
	// output(A);
	if(ans>res)return;
	if(d==n+1){
		res=ans;
		// E(i, n)cout<<path[i]<<' ';
		// cout<<'\n';
		return;
	}
	for(int sta=bj,tmp;sta|(tmp=sta&-sta);sta^=tmp){
		int nst=st|tmp,nbj=bj^tmp;
		int x=te[tmp];
		ans=max(ans,t[x][d]);
		Ed{
			int j=e[i];
			if(!(st>>(j-1)&1))nbj|=1<<(j-1);
		}
		dfs(d+1,nst,nbj,ans);
	}
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
	#endif
	#ifdef ONLINE_JUDGE
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	#endif
	// cout<<calc(1,12,1,1)<<'\n';
	// return 0;
	cin>>n;
	E(i, n)cin>>a[i]>>b[i]>>c[i],n<=20&&(h[i]=-1);
	if(n<=20){
		L(i, n)te[1<<i]=i+1;
		E(i, n)
			E(j, n)t[i][j]=calc(j,a[i],b[i],c[i]);
		E(i, n-1){
			int a,b;
			cin>>a>>b;
			add(a,b),add(b,a);
		}
		// cout<<ne[4]<<'\n';
		// return 0;
		int x=1,st=0;
		Ed{
			int j=e[i];
			st^=1<<(j-1);
		}
		dfs(2,1,st,calc(1,a[1],b[1],c[1]));
		cout<<res<<'\n';
		return 0;
	}
	res=0;
	E(i, n)res=max(res,calc(i,a[i],b[i],c[i]));
	cout<<res<<'\n';
	return 0;
}

以上代码在 ans（dfs中的变量）的更新中，我依次枚举选择扩展哪一个点，但是我却直接将 ans 更新了，这应该会导致下一种转移的答案出错，但是这样写却能够得到前面的20分。 我认为下面的写法才是对的

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l,i##end=r;i<i##end;++i)
#define Rs(i,l,r) for(int i=l,i##end=r;i>i##end;--i)
#define Le(i,l,r) for(int i=l,i##end=r;i<=i##end;++i)
#define Re(i,l,r) for(int i=l,i##end=r;i>=i##end;--i)
#define L(i,l) for(int i=0,i##end=l;i<i##end;++i)
#define E(i,l) for(int i=1,i##end=l;i<=i##end;++i)
#define W(t) while(t--)
#define Wh while

const int N=25,M=2*N,inf=1e9,K=100010;
int n,h[N],e[M],ne[M],idx,b[K],c[K],res=inf,t[N][N],te[1<<20];
ll a[K];
// int path[N]{0,1};//don't forget memset h!
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int calc(ll x,ll a,ll b,ll c){
	// cout<<x<<' '<<a<<' '<<b<<' '<<c<<'\n';
	/*
	head:b+cx
	c>=0 b+cx,b+c(x+1),b+c(x+2),...,b+c*mid,等差数列求和即可
	c<0 b+tc>0     tc > -b    t < -b/c(ceil)
	
	she t=-b/c
		day < t    等差数列求和即可
		day>=t 前t-1项+(day-(t-1))
	*/
	ll head=b+c*x;
	if(head<1)return x+a-1;
	ll t=c<0?(b+(-c-1))/-c:-1,l=x,r=inf;
	__int128 fr=((__int128)t-x)*(head+b+c*(t-1))>>1;
	if(~t&&fr<=a)
		return t-1+a-fr;
	ll front=fr;
	Wh(l<r){
		__int128 mid=l+r>>1,res;
		if(c>=0||mid<t)res=(mid-x+1)*(b+b+c*(x+mid))>>1;
		else res=front+mid-t+1;
		if(res>=a)r=mid;
		else l=mid+1;
	}
	return r;
}
bool st[N]{0,1};
void dfs(int d,int st,int bj,int ans){
	// output(A);
	if(ans>res)return;
	if(d==n+1){
		res=ans;
		// E(i, n)cout<<path[i]<<' ';
		// cout<<'\n';
		return;
	}
	for(int sta=bj,tmp;sta|(tmp=sta&-sta);sta^=tmp){
		int nst=st|tmp,nbj=bj^tmp;
		int x=te[tmp];
		int nans=max(ans,t[x][d]);
		Ed{
			int j=e[i];
			if(!(st>>(j-1)&1))nbj|=1<<(j-1);
		}
		dfs(d+1,nst,nbj,nans);
	}
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
	#endif
	#ifdef ONLINE_JUDGE
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	#endif
	// cout<<calc(1,12,1,1)<<'\n';
	// return 0;
	cin>>n;
	E(i, n)cin>>a[i]>>b[i]>>c[i],n<=20&&(h[i]=-1);
	if(n<=20){
		L(i, n)te[1<<i]=i+1;
		E(i, n)
			E(j, n)t[i][j]=calc(j,a[i],b[i],c[i]);
		E(i, n-1){
			int a,b;
			cin>>a>>b;
			add(a,b),add(b,a);
		}
		// cout<<ne[4]<<'\n';
		// return 0;
		int x=1,st=0;
		Ed{
			int j=e[i];
			st^=1<<(j-1);
		}
		dfs(2,1,st,calc(1,a[1],b[1],c[1]));
		cout<<res<<'\n';
		return 0;
	}
	res=0;
	E(i, n)res=max(res,calc(i,a[i],b[i],c[i]));
	cout<<res<<'\n';
	return 0;
}

但是下面的写法无法通过#1 ~ #4，只能通过#3,请大佬帮我看看第一份代码的正确性是否有问题？如果有，怎么优化第二份代码使其能够通过#1 ~ #4？