最近在做些树形DP练练手
大意就是给你一棵树，你可以断开任意数量的边，使得剩下的联通块大小乘积最大。样例
8
1 2 1 3 2 4 2 5 3 6 3 7 6 8输出
18
我首先想的是设\(f[i]\)表示以\(i\)为根的子树可获得的最大收益，但是会发现这样无法转移。考虑再加一维，\(f[i][j]\)表示以\(i\)的子树中，\(i\)所在的联通块大小为\(j\)的最大价值。然后我就傻了，想了半天也没想起来怎么转移，最后只好看了一眼题解。其实转移好简单的，貌似是个树上背包？考虑在\(dfs\)的过程中进行\(DP\)，每当访问完一个点\(i\)的子结点时，累加一下\(sz[i]\)，就枚举\(j\)，并且用当前子结点的\(DP\)值来更新\(f[i][j]\)。转移方程大概会长成下面这个样子：#includeusing namespace std;#define N 700#define ll long longint n, eid, sz[N+5], head[N+5];ll f[N+5][N+5];struct Edge { int next, to;}e[2*N+5];void addEdge(int u, int v) { e[++eid].next = head[u]; e[eid].to = v; head[u] = eid;}void dp(int u, int fa) { sz[u] = 1, f[u][0] = f[u][1] = 1; for(int i = head[u]; i; i = e[i].next) { int v = e[i].to; if(v == fa) continue; dp(v, u); sz[u] += sz[v]; for(int j = sz[u]; j >= 1; --j) { //枚举i所在的联通块大小 for(int k = min(j, sz[u]-sz[v]); k >= max(1, j-sz[v]); --k) { //枚举子树根结点所在联通块大小 f[u][j] = max(f[u][j], f[u][k]*f[v][j-k]); } } } for(int i = 1; i <= sz[u]; ++i) f[u][0] = max(f[u][0], f[u][i]*i);}int main() { cin >> n; for(int i = 1, x, y; i <= n-1; ++i) cin >> x >> y, addEdge(x, y), addEdge(y, x); dp(1, 0); cout << f[1][0] << endl; return 0;}
但是一交上去只有30\(pts\)，一看讨论区，发现还要用高精度！于是粘了个板子上去，然后就开心的\(MLE\)了￣▽￣。最后把\(int\)换成\(short\)就对了，无语。
粘一下\(AC\)代码#include#include #include using namespace std;#define N 700int n, eid;short sz[N+5], head[N+5];struct Edge { int next, to;}e[2*N+5]; struct bign{ //高精类模板，网上找的 static const int maxn = 120; short d[maxn+5]; short len; void clean() { while(len > 1 && !d[len-1]) len--; } bign() { memset(d, 0, sizeof(d)); len = 1; } bign(int num) { *this = num; } bign(char* num) { *this = num; } bign operator = (const char* num) { memset(d, 0, sizeof(d)); len = strlen(num); for(int i = 0; i < len; i++) d[i] = num[len-1-i] - '0'; clean(); return *this; } bign operator = (int num){ char s[20]; sprintf(s, "%d", num); *this = s; return *this; } bign operator + (const bign& b) { bign c = *this; int i; for(i = 0; i < b.len; i++) { c.d[i] += b.d[i]; if (c.d[i] > 9) c.d[i] %= 10, c.d[i+1]++; } while (c.d[i] > 9) c.d[i++] %= 10, c.d[i]++; c.len = max(len, b.len); if (c.d[i] && c.len <= i) c.len = i+1; return c; } bign operator - (const bign& b) { bign c = *this; int i; for(i = 0; i < b.len; i++) { c.d[i] -= b.d[i]; if (c.d[i] < 0) c.d[i] += 10, c.d[i+1]--; } while (c.d[i] < 0) c.d[i++] += 10, c.d[i]--; c.clean(); return c; } bign operator * (const bign& b) const { int i, j; bign c; c.len = len + b.len; for(j = 0; j < b.len; j++) for(i = 0; i < len; i++) c.d[i+j] += d[i]*b.d[j]; for(i = 0; i < c.len-1; i++) c.d[i+1] += c.d[i]/10, c.d[i] %= 10; c.clean(); return c; } bign operator / (const bign& b) { int i, j; bign c = *this, a = 0; for(i = len - 1; i >= 0; i--) { a = a*10 + d[i]; for (j = 0; j < 10; j++) if (a < b*(j+1)) break; c.d[i] = j; a = a - b*j; } c.clean(); return c; } bign operator % (const bign& b) { int i, j; bign a = 0; for(i = len - 1; i >= 0; i--) { a = a*10+d[i]; for(j = 0; j < 10; j++) if (a < b*(j+1)) break; a = a-b*j; } return a; } bign operator += (const bign& b) { *this = *this+b; return *this; } bool operator <(const bign& b) const { if(len != b.len) return len < b.len; for(int i = len-1; i >= 0; i--) if(d[i] != b.d[i]) return d[i] < b.d[i]; return false; } bool operator >(const bign& b) const { return b < *this; } bool operator <= (const bign& b) const { return !(b < *this); } bool operator >= (const bign& b) const { return !(*this < b); } bool operator != (const bign& b) const { return b < *this || *this < b; } bool operator == (const bign& b) const { return !(b < *this) && !(b > *this); } string str() const { char s[maxn] = {}; for(int i = 0; i < len; i++) s[len-1-i] = d[i]+'0'; return s; }}f[N+5][N+5]; istream& operator >> (istream& in, bign& x) { string s; in >> s; x = s.c_str(); return in;} ostream& operator << (ostream& out, const bign& x) { out << x.str(); return out;}void addEdge(int u, int v) { e[++eid].next = head[u]; e[eid].to = v; head[u] = eid;}void dp(int u, int fa) { sz[u] = 1, f[u][0] = f[u][1] = 1; for(int i = head[u]; i; i = e[i].next) { int v = e[i].to; if(v == fa) continue; dp(v, u); sz[u] += sz[v]; for(int j = sz[u]; j >= 1; --j) { for(int k = min(j, sz[u]-sz[v]); k >= max(1, j-sz[v]); --k) { f[u][j] = max(f[u][j], f[u][k]*f[v][j-k]); } } } for(int i = 1; i <= sz[u]; ++i) f[u][0] = max(f[u][0], f[u][i]*i);}int main() { cin >> n; for(int i = 1, x, y; i <= n-1; ++i) cin >> x >> y, addEdge(x, y), addEdge(y, x); dp(1, 0); cout << f[1][0] << endl; return 0;}