题解 P1623 【[CEOI2007]树的匹配Treasury】

· · 题解

个人觉得树上背包的做法更为易懂，并且只需要高精度加法和乘法。

我们令 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 分代码：

#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 的。但是很松，所以跑得很快。

代码：

#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;
}