题解 P1623 【[CEOI2007]树的匹配Treasury】
xtx1092515503
2020-12-01 21:24:23
个人觉得树上背包的做法更为易懂，并且只需要高精度加法和乘法。
------------
我们令 $f[i,j,0/1]$ 表示 $i$ 的子树中有 $j$ 个匹配，且 $i$ 本身没有/有匹配的方案数。再令 $g[i,0/1]$ 表示没有/有匹配时的最大匹配数。显然，当合并父亲 $x$ 和儿子 $y$ 时，就直接拿 $f[x]$ 和 $f[y]$ 做一下背包即可。
注意，当父亲和儿子均没有匹配时（即 $f[x,?,0]$ 与 $f[y,?,0]$），它可以直接转移到 $f[x,?+?+1,1]$，即在父子间产生一对匹配（当然，也可以选择不用这一对匹配）。其余情况下，以父亲是否有匹配为准。
这里先贴出使用```long long```的 $60$ 分代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,g[1010][2];
ll f[1010][510][2],h[1010][2];
//f[i,j,0/1]:the number of situations when there're j matchings in subtree i and i itself isn't/is matched; and g is the maximal matchings. h is an array for assistance.
vector<int>v[1010];
bool occ[1010];
void dfs(int x){
f[x][0][0]=1;
for(auto y:v[x]){
dfs(y);
int tmp0=g[x][0]+max(g[y][0],g[y][1]),tmp1=max(g[x][1]+max(g[y][0],g[y][1]),g[x][0]+g[y][0]+1);
for(int i=0;i<=tmp0;i++)h[i][0]=0;
for(int i=0;i<=tmp1;i++)h[i][1]=0;
for(int i=0;i<=g[x][0];i++)for(int j=0;j<=g[y][0];j++)h[i+j][0]+=f[x][i][0]*f[y][j][0],h[i+j+1][1]+=f[x][i][0]*f[y][j][0];
for(int i=0;i<=g[x][1];i++)for(int j=0;j<=g[y][0];j++)h[i+j][1]+=f[x][i][1]*f[y][j][0];
for(int i=0;i<=g[x][0];i++)for(int j=0;j<=g[y][1];j++)h[i+j][0]+=f[x][i][0]*f[y][j][1];
for(int i=0;i<=g[x][1];i++)for(int j=0;j<=g[y][1];j++)h[i+j][1]+=f[x][i][1]*f[y][j][1];
for(int i=0;i<=tmp0;i++)f[x][i][0]=h[i][0];
for(int i=0;i<=tmp1;i++)f[x][i][1]=h[i][1];
g[x][0]=tmp0;
g[x][1]=tmp1;
}
}
int main(){
scanf("%d",&n);
for(int i=1,x,y,z;i<=n;i++){
scanf("%d%d",&x,&y);
while(y--)scanf("%d",&z),v[x].push_back(z),occ[z]=true;
}
for(int i=1;i<=n;i++){
if(occ[i])continue;
dfs(i);
int mx=max(g[i][0],g[i][1]);
ll ret=0;
if(mx==g[i][0])ret+=f[i][g[i][0]][0];
if(mx==g[i][1])ret+=f[i][g[i][1]][1];
printf("%d\n%lld\n",mx,ret);
}
return 0;
}
```
剩下的部分需要高精度。但明显，上述算法本身复杂度已经达到 $O(n^2)$，假如再套上高精度不大可能过去（根据极不靠谱的估算，高精度最大可能会有 $2^{333}\approx10^{100}$ 的位数，因为还要用乘法，所以就更不靠谱了）。当然，有胆大的可以尝试用FFT优化背包的卷积和高精度的卷积，但 $100,1000$ 这么点大的卷积可能用不用FFT效果都没啥区别。
那怎么办呢？
观察到我们只需要求最大的方案数。这意味着我们只需要记录最大值附近的几个DP值即可——剩余的DP值无论怎么搞都不可能最终成为最大值。于是这样搞正常DP的复杂度就被优化到了 $O(n)$。套上高精度，上限约是 $1000\times 100^2=10^8$ 的。但是很松，所以跑得很快。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,g[1010][2];
struct Wint:vector<int>{
Wint(){clear();}
Wint(int x){clear();while(x)push_back(x%10),x/=10;}
void operator ~(){
for(int i=0;i+1<size();i++)(*this)[i+1]+=(*this)[i]/10,(*this)[i]%=10;
while(!empty()&&back()>9){
int tmp=back()/10;
back()%=10;
push_back(tmp);
}
while(!empty()&&!back())pop_back();
}
void operator +=(const Wint &x){
// print(),putchar('+'),x.print();
if(size()<x.size())resize(x.size());
for(int i=0;i<x.size();i++)(*this)[i]+=x[i];
~*this;
// putchar('='),print(),putchar('\n');
}
friend Wint operator *(const Wint &x,const Wint &y){
// x.print(),putchar('*'),y.print();
Wint z;
if(!x.size()||!y.size())return z;
z.resize(x.size()+y.size()-1);
for(int i=0;i<x.size();i++)for(int j=0;j<y.size();j++)z[i+j]+=x[i]*y[j];
~z;
// putchar('='),z.print(),putchar('\n');
return z;
}
void print()const{
if(empty()){putchar('0');return;}
for(int i=size()-1;i>=0;i--)putchar('0'+(*this)[i]);
}
}f[1010][510][2],h[1010][2];
//f[i,j,0/1]:the number of situations when there're j matchings in subtree i and i itself isn't/is matched; and g is the maximal matchings. h is an array for assistance.
vector<int>v[1010];
bool occ[1010];
void dfs(int x){
f[x][0][0]=1;
for(auto y:v[x]){
dfs(y);
int tmp0=g[x][0]+max(g[y][0],g[y][1]),tmp1=max(g[x][1]+max(g[y][0],g[y][1]),g[x][0]+g[y][0]+1);
for(int i=0;i<=tmp0;i++)h[i][0]=0;
for(int i=0;i<=tmp1;i++)h[i][1]=0;
for(int i=max(0,g[x][0]-1);i<=g[x][0];i++)for(int j=max(0,g[y][0]-1);j<=g[y][0];j++)h[i+j][0]+=f[x][i][0]*f[y][j][0],h[i+j+1][1]+=f[x][i][0]*f[y][j][0];
for(int i=max(0,g[x][1]-1);i<=g[x][1];i++)for(int j=max(0,g[y][0]-1);j<=g[y][0];j++)h[i+j][1]+=f[x][i][1]*f[y][j][0];
for(int i=max(0,g[x][0]-1);i<=g[x][0];i++)for(int j=max(0,g[y][1]-1);j<=g[y][1];j++)h[i+j][0]+=f[x][i][0]*f[y][j][1];
for(int i=max(0,g[x][1]-1);i<=g[x][1];i++)for(int j=max(0,g[y][1]-1);j<=g[y][1];j++)h[i+j][1]+=f[x][i][1]*f[y][j][1];
for(int i=max(0,tmp0-1);i<=tmp0;i++)f[x][i][0]=h[i][0];
for(int i=max(0,tmp1-1);i<=tmp1;i++)f[x][i][1]=h[i][1];
g[x][0]=tmp0;
g[x][1]=tmp1;
}
}
int main(){
scanf("%d",&n);
for(int i=1,x,y,z;i<=n;i++){
scanf("%d%d",&x,&y);
while(y--)scanf("%d",&z),v[x].push_back(z),occ[z]=true;
}
for(int i=1;i<=n;i++){
if(occ[i])continue;
dfs(i);
int mx=max(g[i][0],g[i][1]);
Wint ret;
if(mx==g[i][0])ret+=f[i][g[i][0]][0];
if(mx==g[i][1])ret+=f[i][g[i][1]][1];
printf("%d\n",mx);
ret.print();
}
return 0;
}
```