萌新10分代码求助
  • 板块P1411 树
  • 楼主hywake
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/10/18 19:28
  • 上次更新2023/11/2 13:01:41
查看原帖
萌新10分代码求助
1137971
hywake楼主2023/10/18 19:28
#include<bits/stdc++.h>
using namespace std;
long long n,m,k,fa[705],x,y,ma[705],l[705][705],q[705],opp;
short dp[705][705][105],qq[705][105],mm[105],op[105];
vector<long long> vc[705];
void qing(){
	for(int i=1;i<=opp;++i) op[i]=0;
	opp=0;
}
void suan1(long long x){
	for(int i=1;i<=l[y][x];++i){
		op[i]=dp[y][x][i]*x;
	}
	opp=l[y][x];
	for(int i=1;i<=opp;++i){
		op[i+1]+=op[i]/10;
		op[i]%=10;
		if(i==opp&&op[i+1]) opp++;
	}
	if(opp>m){
		m=opp;
		for(int i=1;i<=m;++i) mm[i]=op[i];
	}
	else if(opp==m){
		for(int i=m;i>0;--i){
			if(mm[i]>op[i]) break;
			else if(op[i]>mm[i]){
				for(int j=i;j>0;--j) mm[j]=op[j];
				break;
			}
		}
	}
}
void suan2(long long x){
	for(int i=1;i<=q[x];++i) qq[x][i]=0;
	q[x]=0;
	for(int i=1;i<=l[fa[y]][x];++i){
		for(int j=1;j<=m;++j)
		qq[x][i+j-1]+=dp[fa[y]][x][i]*mm[j];
	}
	q[x]=l[fa[y]][x]+m-1;
	for(int i=1;i<=q[x];++i){
		qq[x][i+1]+=qq[x][i]/10;
		qq[x][i]%=10;
		if(i==q[x]&&qq[x][i+1]) q[x]++;
	}	
}
void suan3(long long a,long long b){
	for(int i=1;i<=l[fa[y]][a];++i){
		for(int j=1;j<=l[y][b];++j){
			op[i+j-1]=dp[fa[y]][a][i]*dp[y][b][j];
		}
	}
	opp=l[fa[y]][a]+l[y][b]-1;
	for(int i=1;i<=opp;++i){
		op[i+1]+=op[i]/10;
		op[i]%=10;
		if(i==opp&&op[i+1]) opp++;
	}	
	if(opp>q[a+b]){
		q[a+b]=opp;
		for(int i=1;i<=q[a+b];++i) qq[a+b][i]=op[i];
	}
	else if(opp==q[a+b]){
		for(int i=q[a+b];i>0;--i){
			if(qq[a+b][i]>op[i]) break;
			else if(op[i]>qq[a+b][i]){
				for(int j=i;j>0;--j) qq[a+b][j]=op[j];
				break;
			}
		}
	}
}
void suan4(long long x){
	l[fa[y]][x]=q[x];
	for(int i=1;i<=q[x];++i){
		dp[fa[y]][x][i]=qq[x][i];
	}
}
void qingm(){
	for(int i=1;i<=m;++i) mm[i]=0;
	m=0;
}
void sou(long long x){
	for(int i=0;i<vc[x].size();++i){
		sou(vc[x][i]);
	}
	qingm();y=x;
	for(int i=ma[x];i>0;--i) {
		qing();
		suan1(i);
	}
	for(int i=ma[fa[x]];i>0;--i){
		qing();
		suan2(i);
		for(int j=1;j<=ma[x];++j){
			if(i+j>n) break;
			qing();
			suan3(i,j);
//			qq[i+j]=max(qq[i+j],dp[x][j]*dp[fa[x]][i]);
		}
	}
	ma[fa[x]]=min(n,ma[fa[x]]+ma[x]);
	for(int i=ma[fa[x]];i>0;--i) {
		suan4(i);
//		cout<<i<<" ";
//		for(int j=q[i];j>0;--j) cout<<qq[i][j];
//		cout<<endl;
	}
//	cout<<endl;
}
int main(){
	cin>>n;dp[n][1][1]=1;ma[n]=1;l[n][1]=1;
	for(int i=1;i<n;++i){
		dp[i][1][1]=1;ma[i]=1;l[i][1]=1;
		cin>>x>>y;
		fa[max(x,y)]=min(x,y);
		vc[min(x,y)].push_back(max(x,y));
	}
	sou(1);
	for(int i=m;i>0;--i) cout<<mm[i];
}
2023/10/18 19:28
加载中...