TopCoder SRM 570 Div1 550 CentaurCompany

TopCoder SRM 570 Div1 550 CentaurCompany

和Div2的1000类型差不多，都是个很套路的树形DP
我的做法暴力得要死，天晓得怎么过的。。
f[0/1][i][j][k][l] f [ 0 / 1 ] [ i ] [ j ] [ k ] [ l ] $f[0/1][i][j][k][l]$，0/1表示第 i i $i$个节点在哪个公司，j" role="presentation" style="position: relative;">jj$j$表示 human h u m a n $human$公司有几人， k k $k$表示human" role="presentation" style="position: relative;">humanhuman$human$公司有几个联通块， l l $l$表示horse" role="presentation" style="position: relative;">horsehorse$horse$公司有几个联通块， f f <script type="math/tex" id="MathJax-Element-9">f</script>数组中存的是方案数。
后来看了一下别人的代码意识到似乎可以把两个公司看成相互独立的，就可以简化很多。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=37;
const int M=N<<1;
int sz[N],n;
ll f[2][N][N][N][N],d[2][N][N][N];
int head[N],Next[M],v[M],cnt;class CentaurCompany {
public:double getvalue( vector <int> a, vector <int> b );
};void add(int x,int y){Next[++cnt]=head[x];head[x]=cnt;v[cnt]=y;
}int get(int n,int k){if (n>=2*(k-1)) return 0;return 2*(k-1)-n;
}void dfs(int x,int fa){sz[x]=1;f[1][x][1][1][0]=1;f[0][x][0][0][1]=1;for(int i=head[x];i!=-1;i=Next[i])if (v[i]!=fa){dfs(v[i],x);memset(d,0,sizeof d);for(int j=0;j<=sz[x];j++)for(int k=0;k<=j;k++)for(int l=0;l<=sz[x]-j;l++)for(int u=0;u<=sz[v[i]];u++)for(int y=0;y<=u;y++)for(int z=0;z<=sz[v[i]]-u;z++){d[1][j+u][k+y][l+z]+=f[1][x][j][k][l]*f[0][v[i]][u][y][z];d[0][j+u][k+y][l+z]+=f[0][x][j][k][l]*f[1][v[i]][u][y][z];if (k+y) d[1][j+u][k+y-1][l+z]+=f[1][x][j][k][l]*f[1][v[i]][u][y][z];if (l+z) d[0][j+u][k+y][l+z-1]+=f[0][x][j][k][l]*f[0][v[i]][u][y][z];}sz[x]+=sz[v[i]];for(int j=0;j<=sz[x];j++)for(int k=0;k<=j;k++)for(int l=0;l<=sz[x]-j;l++)f[0][x][j][k][l]=d[0][j][k][l],f[1][x][j][k][l]=d[1][j][k][l];}
}double CentaurCompany::getvalue(vector <int> a, vector <int> b) {n=a.size()+1;cnt=0;memset(head,-1,sizeof head);memset(f,0,sizeof f);for(int i=0;i<n-1;i++)add(a[i],b[i]),add(b[i],a[i]);dfs(1,0);ll sum=1LL<<n;double ans=0;ll s=0;for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)for(int k=1;k<=n-i;k++){int v=get(i,j)+get(n-i,k);ans+=1.0*v*(f[1][1][i][j][k]+f[0][1][i][j][k])/sum;s+=f[1][1][i][j][k]+f[0][1][i][j][k];}//cout<<s<<endl<<sum;return ans;
}