luogu P1623 [CEOI2007]树的匹配Treasury

题目链接

题解

f[i][0/1]表示当前位置没用/用了

转移暴力就可以了
code

// luogu-judger-enable-o2

#include<vector>

#include<cstdio>

#include<cstring>

#include<algorithm>

using std::vector;

using std::max;

using std::min;

inline int read() {

    int x=0,f=1;

    char c=getchar();

    while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar() ;}

    while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar() ;

    return x*f;

}

const int maxn = 1007;

struct node{

    int v,next;

}edge[maxn];

int dp[maxn][2],head[maxn],num=0;

inline void add_edge(int u,int v) {

    edge[++num].v=v;edge[num].next=head[u];head[u]=num;

}

int n;

void init() {

    n=read();

    for(int num,k,i=1;i<=n;++i)  {

        k=read(),num=read();

        for(int j=1;j<=num;++j)

            add_edge(k,read());

    }

}

struct Int {

     static const int Bit=1e4;//压3位

    int a[107],size;

    inline void operator = (const int &x) {

        memset(a,0,sizeof a) ;a[size=1]=x;

    }

    inline Int operator + (const Int t ) {

        Int c=*this;

        int sz =max(c.size,t.size);

        for(int i=1;i<=sz;++i)

            c.a[i]+=t.a[i],c.a[i+1]+=c.a[i]/Bit,c.a[i]%=Bit;

        if(c.a[sz+1])sz++;

        c.size=sz;

        return c;

    }

    inline Int operator * (const Int t) {

        int sz=size+t.size-1;

        Int c;c=0;

        for(int i=1;i<=size;++i)

            for(int j=1;j<=t.size;++j)

                c.a[i+j-1]+=a[i]*t.a[j];

        for(int i=1;i<=sz;++i)

            c.a[i+1]+=c.a[i]/Bit,c.a[i]%=Bit;

        if(c.a[sz+1])sz++;c.size=sz;

        return c;//XD

    }

    inline void print() {

        printf("%d",a[size]);

        for(int i=size-1;i;--i)

            printf("%04d",a[i]);

    }

}cnt[maxn][2];

inline void operator *= (Int &a,Int b) {a=a*b;}

inline void operator += (Int &a,Int b) {a=a+b;}

void dfs(int x) {

    //int num = vec[x].size();

    cnt[x][0]=1;cnt[x][1]=1;

    for(int i=head[x];i;i=edge[i].next) {

        int v=edge[i].v;

        dfs(v);

        if(dp[x][1]) {

            dp[x][1]+=dp[v][1];

            if(dp[v][0]!=dp[v][1]) cnt[x][1]*=cnt[v][1];

            else cnt[x][1]*=cnt[v][0]+cnt[v][1];

        }

        if(dp[x][0]+dp[v][0]+1 > dp[x][1]) dp[x][1] = dp[x][0]+dp[v][0]+1,cnt[x][1]=cnt[x][0]*cnt[v][0];

        else if(dp[x][0]+dp[v][0]+1 == dp[x][1]) cnt[x][1] += cnt[x][0]*cnt[v][0];

        dp[x][0]+=dp[v][1];

        if(dp[v][0]!=dp[v][1]) cnt[x][0]*=cnt[v][1];

        else cnt[x][0]*=cnt[v][0]+cnt[v][1];

    }

    if(!dp[x][1]) cnt[x][1]=0;

}

int main() {

    init();

    dfs(1);

    printf("%d\n",dp[1][1]);

    if(dp[1][1]!=dp[1][0]) cnt[1][1].print();

    else cnt[1][1]+=cnt[1][0],cnt[1][1].print();

    return 0;

}
巴特西

luogu P1623 [CEOI2007]树的匹配Treasury

题目链接

题解

code

最新文章

热门文章
