洛谷 P1411 树 (树形dp)

大意: 给定树, 求删除一些边, 使得连通块大小的乘积最大

设$dp_{i,j}$表示只考虑点$i$的子树, $i$所在连通块大小为$j$的最大值.

转移的时候不计算$i$所在连通块的贡献, 留到最后再算.

这题答案很大, 还要套个高精, 这是没套高精的代码

#include <iostream>

#include <sstream>

#include <algorithm>

#include <cstdio>

#include <cmath>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <cstring>

#include <bitset>

#include <functional>

#include <random>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

#define hr putchar(10)

#define pb push_back

#define lc (o<<1)

#define rc (lc|1)

#define mid ((l+r)>>1)

#define ls lc,l,mid

#define rs rc,mid+1,r

#define x first

#define y second

#define io std::ios::sync_with_stdio(false)

#define endl '\n'

#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<',';hr;})

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

const int P = 1e9+7, INF = 0x3f3f3f3f;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}

ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}

inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}

//head

const int N = 710;

int n, sz[N];

vector<int> g[N];

int dp[N][N],tmp[N];

void chkmax(int &a, int b) {a<b?a=b:0;}

void dfs(int x, int f) {

	sz[x] = dp[x][1] = 1;

	for (int y:g[x]) if (y!=f) {

		dfs(y,x);

		REP(i,1,sz[x]+sz[y]) tmp[i]=0;

		REP(i,1,sz[x]) REP(j,1,sz[y]) {

			int t = dp[x][i]*dp[y][j];

			chkmax(tmp[i],t*j);

			chkmax(tmp[i+j],t);

		}

		REP(i,1,sz[x]+sz[y]) dp[x][i]=tmp[i];

		sz[x] += sz[y];

	}

}

int main() {

	scanf("%d",&n);

	REP(i,2,n) {

		int u, v;

		scanf("%d%d",&u,&v);

		g[u].pb(v),g[v].pb(u);

	}

	dfs(1,0);

	int ans = 0;

	REP(i,1,n) ans = max(ans, dp[1][i]*i);

	printf("%d\n", ans);

}