BigInt+dfs版
2025-09-17 13:04:31
发布于:湖北
6阅读
0回复
0点赞
class BigInt {
public:
vector<int> digits; // 存储大整数的每一位数字,按低位到高位排列
BigInt() {} // 默认构造函数
BigInt(int n) { // 从整数构造BigInt
if (n == 0) digits.push_back(0); // 处理0的情况
else {
while (n) { // 分解整数到各位数字
digits.push_back(n % 10);
n /= 10;
}
}
}
BigInt operator*(const BigInt& other) const { // 大整数乘法
BigInt res;
res.digits.resize(digits.size() + other.digits.size(), 0); // 预分配空间
for (int i = 0; i < digits.size(); i++) {
int carry = 0; // 进位
for (int j = 0; j < other.digits.size(); j++) {
int product = digits[i] * other.digits[j] + res.digits[i + j] + carry;
carry = product / 10; // 计算进位
res.digits[i + j] = product % 10; // 计算当前位
}
if (carry) { // 处理最高位的进位
res.digits[i + other.digits.size()] += carry;
}
}
while (res.digits.size() > 1 && res.digits.back() == 0) { // 去除前导零
res.digits.pop_back();
}
return res;
}
bool operator<(const BigInt& other) const { // 大整数比较
if (digits.size() != other.digits.size()) {
return digits.size() < other.digits.size(); // 位数少的更小
}
for (int i = digits.size() - 1; i >= 0; i--) { // 从高位到低位比较
if (digits[i] != other.digits[i]) {
return digits[i] < other.digits[i];
}
}
return false; // 相等
}
string str() const { // 转换为字符串
string s;
for (int i = digits.size() - 1; i >= 0; i--) {
s += to_string(digits[i]);
}
return s;
}
};
void dfs(int u, int parent) {
size[u] = 1; // 初始化当前子树的大小为1(只有节点u自己)
dp[u][1] = BigInt(1); // 初始状态:不删除任何边时,连通块大小为1,乘积为1
for (int v : tree[u]) { // 遍历u的所有子节点
if (v == parent) continue; // 跳过父节点,避免回环
dfs(v, u); // 递归处理子节点v的子树
BigInt temp[MAXN]; // 临时数组,用于存储更新后的dp值
// 遍历u当前所有可能的连通块大小i
for (int i = size[u]; i >= 1; i--) {
// 遍历v子树所有可能的连通块大小j
for (int j = size[v]; j >= 1; j--) {
// 如果dp[u][i]或dp[v][j]为0,跳过(无效状态)
if (dp[u][i].digits.size() == 1 && dp[u][i].digits[0] == 0) continue;
if (dp[v][j].digits.size() == 1 && dp[v][j].digits[0] == 0) continue;
// 情况1:断开u和v之间的边
// v的子树成为独立连通块,大小为j,贡献乘积为dp[v][j] * j
BigInt disconnect = dp[u][i] * dp[v][j] * BigInt(j);
if (temp[i] < disconnect) {
temp[i] = disconnect;
}
// 情况2:不断开u和v之间的边
// u和v的连通块合并,大小为i + j,乘积为dp[u][i] * dp[v][j]
BigInt connect = dp[u][i] * dp[v][j];
if (temp[i + j] < connect) {
temp[i + j] = connect;
}
}
}
size[u] += size[v]; // 更新u的子树大小(包含v的子树)
// 用temp数组更新dp[u]
for (int i = 1; i <= size[u]; i++) {
if (temp[i].digits.size() > 1 || temp[i].digits[0] != 0) {
dp[u][i] = temp[i];
}
}
}
}
int main() {
cin >> n; // 读取节点数
tree.resize(n + 1); // 初始化树的邻接表
// 读取树的边
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}
// 初始化dp数组为0
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= n; j++) {
dp[i][j] = BigInt(0);
}
}
dfs(1, -1); // 从根节点1开始DFS,父节点为-1(表示无父节点)
BigInt ans(0); // 初始化最大乘积为0
// 遍历根节点所有可能的连通块大小,计算最大乘积
for (int i = 1; i <= n; i++) {
BigInt candidate = dp[1][i] * BigInt(i); // dp[1][i] * i
if (ans < candidate) {
ans = candidate;
}
}
cout << ans.str() << endl; // 输出结果
return 0;
}
这里空空如也


有帮助,赞一个