求调玄关
  • 板块P1411 树
  • 楼主System_Error_/se
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/7/16 09:49
  • 上次更新2024/7/16 09:50:33
查看原帖
求调玄关
812955
System_Error_/se楼主2024/7/16 09:49

只AC#1,其余TLE+WA

压位高精是抄这个的

玄关

#include<bits/stdc++.h>
using namespace std;
const int N=705;
vector<int> v[N];
int n,sz[N];
const int base = 100000000;
int cnt;
struct BigInteger {

	vector<int> ans;
	bool sign;

	BigInteger();
	BigInteger(int);

	bool operator ==(const BigInteger&)const;
	bool operator <(const BigInteger&)const;
	bool operator >(const BigInteger&)const;
	bool operator <=(const BigInteger&)const;
	bool operator >=(const BigInteger&)const;
	bool operator !=(const BigInteger&)const;

	BigInteger operator = (const BigInteger&);
	BigInteger operator - (const BigInteger&) const;
	BigInteger operator + (const BigInteger&) const;
	BigInteger operator * (const BigInteger&) const;
	BigInteger operator * (const int&) const;
	BigInteger operator / (const BigInteger&) const;
	BigInteger operator / (const int&) const;
	BigInteger operator %(const BigInteger&)const;
	int operator % (const int&) const;
	BigInteger operator ^ (const int&) const;

	void operator -=(const BigInteger&);
	void operator +=(const BigInteger&);
	void operator *=(const BigInteger&);
	void operator /=(const BigInteger&);
	void operator %=(const BigInteger&);

	void input(string);
	void output();

}dp[N][N],pw[N];

void div_ans_mod(BigInteger& x) {
	BigInteger p(2);
	pw[0] = BigInteger(1);
	pw[1] = p;
	while (pw[cnt] <= x) {
		++cnt;
		pw[cnt] = p * pw[cnt - 1];
	}
}

BigInteger::BigInteger() {
	sign = true;
	ans.clear();
}

BigInteger::BigInteger(int n) {
	sign = true;
	while (n) {
		ans.push_back(n % base);
		n /= base;
	}
}

void BigInteger::input(string str) {
	int top = str.length() - 1;
	while (top - 7 >= 0) {
		int temp = (str[top] - '0') + (str[top - 1] - '0') * 10 + (str[top - 2] - '0') * 100 + (str[top - 3] - '0') * 1000
			+ (str[top - 4] - '0') * 10000 + (str[top - 5] - '0') * 100000 + (str[top - 6] - '0') * 1000000 + (str[top - 7] - '0') * 10000000;
		top -= 8;
		ans.push_back(temp);
	}
	if (top >= 0) {
		int temp = 0;
		for (int i = 0; i <= top; i++) {
			temp = temp * 10 + (str[i] - '0');
		}
		ans.push_back(temp);
	}
}

void BigInteger::output() {
	if (sign == false) cout << "-";
	for (int i = ans.size() - 1; i > 0; i--) {
		if (ans[i] == 0) ans.pop_back();
		else break;
	}
	printf("%lld", ans.back());
	ans.pop_back();
	while (!ans.empty()) {
		printf("%08d", ans.back());
		ans.pop_back();
	}
	printf("\n");
}

bool BigInteger:: operator==(const BigInteger& x) const {
	if (ans.size() != x.ans.size()) return false;
	for (int i = ans.size() - 1; i >= 0; i--) {
		int a = ans[i];
		int b = x.ans[i];
		if (a != b) return false;
	}
	return true;
}

bool BigInteger::operator!=(const BigInteger& x)const {
	return !(x == *this);
}

bool BigInteger:: operator<(const BigInteger& x) const {
	if (ans.size() != x.ans.size()) return ans.size() < x.ans.size();
	for (int i = ans.size() - 1; i >= 0; i--) {
		int a = ans[i];
		int b = x.ans[i];
		if (a >= b) return false;
		if (a < b) return true;
	}
	return false;
}

bool BigInteger:: operator>(const BigInteger& x) const {
	if (ans.size() != x.ans.size()) return ans.size() > x.ans.size();
	for (int i = ans.size() - 1; i >= 0; i--) {
		int a = ans[i];
		int b = x.ans[i];
		if (a > b) return true;
		if (a <= b) return false;
	}
	return false;
}

bool BigInteger:: operator<=(const BigInteger& x) const {
	if (ans.size() != x.ans.size()) return ans.size() < x.ans.size();
	for (int i = ans.size() - 1; i >= 0; i--) {
		int a = ans[i];
		int b = x.ans[i];
		if (a > b) return false;
		if (a < b) return true;
	}
	return true;
}

bool BigInteger:: operator>=(const BigInteger& x) const {
	if (ans.size() != x.ans.size()) return ans.size() < x.ans.size();
	for (int i = ans.size() - 1; i >= 0; i--) {
		int a = ans[i];
		int b = x.ans[i];
		if (a > b) return true;
		if (a < b) return false;
	}
	return true;
}

BigInteger BigInteger :: operator +(const BigInteger& x) const {
	int mod = 0;
	BigInteger ret;
	int len = max(ans.size(), x.ans.size());
	for (int i = 0; i < len; i++) {
		mod += (i < ans.size()) ? ans[i] : 0;
		mod += (i < x.ans.size()) ? x.ans[i] : 0;
		ret.ans.push_back(mod % base);
		mod /= base;
	}
	if (mod) ret.ans.push_back(mod);
	while (ret.ans.size() > 1 && ret.ans.back() == 0)ret.ans.pop_back();
	if (ret.ans.empty())ret.ans.push_back(0);
	return ret;
}

BigInteger BigInteger::operator-(const BigInteger& x)const {
	BigInteger ret;
	bool flag = true;
	if (*this < x)flag = false;
	if (*this == x) {
		ret.ans.push_back(0);
		return ret;
	}
	else {
		int len = max(ans.size(), x.ans.size());
		int mod = 0;
		for (int l = 0; l < len; l++) {
			if (flag) {
				mod += (l < ans.size()) ? ans[l] : 0;
				mod -= (l < x.ans.size()) ? x.ans[l] : 0;
			}
			else {
				mod += (l < x.ans.size()) ? x.ans[l] : 0;
				mod -= (l < ans.size()) ? ans[l] : 0;
			}
			ret.ans.push_back((mod + base) % base);
			if (mod < 0) mod = -1;
			else mod = 0;
		}
		ret.sign = flag;
	}
	while (ret.ans.size() > 1 && ret.ans.back() == 0)ret.ans.pop_back();
	if (ret.ans.empty())ret.ans.push_back(0);
	return ret;
}

BigInteger BigInteger::operator=(const BigInteger& x) {
	ans.clear();
	sign = x.sign;
	for (int i = 0; i < x.ans.size(); i++) {
		ans.push_back(x.ans[i]);
	}
	return *this;
}

BigInteger BigInteger:: operator*(const int& x) const {
	BigInteger ret;
	int len = ans.size();
	for (int i = 0; i <= len; i++) {
		ret.ans.push_back(0);
	}
	int mod = 0;
	for (int i = 0; i < ans.size(); i++) {
		mod += ans[i] * x;
		if (mod >= base) {
			ret.ans[i] = mod % base;
			ret.ans[i + 1] = mod / base;
		}
		else {
			ret.ans[i] = mod;
		}
		mod = 0;
	}
	while (ret.ans.size() > 1 && ret.ans.back() == 0)ret.ans.pop_back();
	if (ret.ans.empty())ret.ans.push_back(0);
	return ret;
}

BigInteger BigInteger::operator*(const BigInteger& x)const {
	BigInteger ret;
	int len1 = ans.size();
	int len2 = x.ans.size();
	int len = len1 + len2;
	for (int i = 0; i <= len; i++) {
		ret.ans.push_back(0);
	}
	int mod = 0;
	for (int i = 0; i < ans.size(); i++) {
		for (int j = 0; j < x.ans.size(); j++) {
			mod += x.ans[j] * ans[i];
			mod += ret.ans[i + j];
			if (mod >= base) {
				ret.ans[i + j] = mod % base;
				ret.ans[i + j + 1] += mod / base;
			}
			else {
				ret.ans[i + j] = mod;
			}
			mod = 0;
		}
	}
	if (sign != x.sign) ret.sign = false;
	while (ret.ans.size() > 1 && ret.ans.back() == 0)ret.ans.pop_back();
	if (ret.ans.empty())ret.ans.push_back(0);
	return ret;
}

BigInteger BigInteger::operator/(const int& x) const {
	BigInteger ret;
	int down = 0;
	int p = 0;
	for (int i = ans.size() - 1; i >= 0; i--) {
		down = ans[i] + down * base;
		if (down == 0 && i) {
			ret.ans.insert(ret.ans.begin(), 0);
		}
		else {
			int in = down / x;
			ret.ans.insert(ret.ans.begin(), in);
			down %= x;
		}
	}
	while (ret.ans.size() > 1 && ret.ans.back() == 0)ret.ans.pop_back();
	if (ret.ans.empty())ret.ans.push_back(0);
	return ret;
}

BigInteger BigInteger::operator /(const BigInteger& x) const {
	BigInteger ret;
	int nod = 0;
	BigInteger temp = *this;
	for (int i = cnt; i >= 0; i--) {
		if (pw[i] * x <= temp) {
			BigInteger t = pw[i] * x;
			ret += pw[i];
			temp -= t;
		}
	}
	if (sign != x.sign) ret.sign = false;
	while (ret.ans.size() > 1 && ret.ans.back() == 0)ret.ans.pop_back();
	if (ret.ans.empty())ret.ans.push_back(0);
	return ret;
}

BigInteger BigInteger::operator%(const BigInteger& x) const {
	BigInteger ret;
	BigInteger temp = *this;
	for (int i = cnt; i >= 0; i--) {
		if (pw[i] * x <= temp) {
			temp -= pw[i] * x;
		}
	}
	ret = temp;
	while (ret.ans.size() > 1 && ret.ans.back() == 0)ret.ans.pop_back();
	if (ret.ans.empty())ret.ans.push_back(0);
	return ret;
}

int BigInteger:: operator%(const int& x)const {
	BigInteger ret;
	int down = 0;
	for (int i = ans.size() - 1; i >= 0; i--) {
		down = ans[i] + down * base;
		down %= x;
	}
	return down;
}

BigInteger BigInteger::operator^(const int& n) const {
	BigInteger ret(1);
	BigInteger temp = *this;
	int pow = n;
	while (pow) {
		if (pow & 1) ret = (ret * temp);
		temp = temp * temp;
		pow >>= 1;
	}
	while (ret.ans.size() > 1 && ret.ans.back() == 0)ret.ans.pop_back();
	if (ret.ans.empty())ret.ans.push_back(0);
	return ret;
}

void BigInteger::operator+=(const BigInteger& x) {
	*this = *this + x;
}

void BigInteger::operator-=(const BigInteger& x) {
	*this = *this - x;
}

void BigInteger::operator*=(const BigInteger& x) {
	*this = *this * x;
}

void BigInteger::operator/=(const BigInteger& x) {
	*this = *this / x;
}

void BigInteger::operator%=(const BigInteger& x) {
	*this = *this % x;
}
void dfs(int x,int pre) {
	dp[x][1]=sz[x]=1;
	for(int i=0; i<v[x].size(); i++) {
		if(v[x][i]==pre) continue;
		dfs(v[x][i],x);
		sz[x]+=sz[v[x][i]];
	}
	for(int i=0; i<v[x].size(); i++) {
		if(v[x][i]==pre) continue;
		for(int j=sz[x]; j>=2; j--)
			for(int k=1; k<=sz[v[x][i]]; k++)
				if(j-k>=1) if(dp[x][j-k]*dp[v[x][i]][k]>dp[x][j]) dp[x][j]=dp[x][j-k]*dp[v[x][i]][k];
		BigInteger mx(0);
		for(int k=1; k<=sz[v[x][i]]; k++) {
			BigInteger tmp(k);
			if(dp[v[x][i]][k]*tmp>mx) mx=dp[v[x][i]][k]*tmp;
		}
		dp[x][1]=dp[x][1]*mx;
	}
}
int main() {
	cin>>n;
	for(int i=1; i<n; i++) {
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,0);
	BigInteger ans(0);
	for(int i=1; i<=n; i++) {
		BigInteger tmp(i);
		if(dp[1][i]*tmp>ans) ans=dp[1][i]*tmp;
	}
	ans.output();
	return 0;
}
2024/7/16 09:49
加载中...