noip模拟赛 hungary

分析：比较难的一道题,看到要求方案数，又是在一棵树上，自然就想起了树形dp.状态该怎么表示呢？首先肯定有一维状态表示以i为根的子树，考虑到i有没有匹配对答案也是有影响的，自然而然状态就出来了：f[i][0/1]表示以i为根的子树中,i取或不取的最大匹配.因为要求方案数，再开一个数组g[i][0/1]记录方案数.

接下来考虑怎么转移.如果i不选，那么它的子节点不管选不选都没关系:

f[i][0] = Σmax{f[j][0],f[j][1]},如果i要选，那么它的子节点中一定有一个没选的点k,其它点随意.

f[i][1] = max{f[k][0] + 1 + Σmax{f[j][0],f[j][1] (j != k)}}.对于g的转移就是比较常见的套路了，子树内加法原理，子树合并乘法原理.每次选肯定要选最大匹配的那种方案，所以开一个数组ans,如果f[i][0] > f[i][1],ans[i] = g[i][0]; f[i][0] < f[i][1],ans[i] = g[i][1];

f[i][0] = f[i][1],ans[i] = g[i][1] + g[i][0]. 那么g[i][0] = πans[j],i要选的话，k就不能直接用ans的值，那么g[i][1] = Σ(g[k][0] * (πans[j] / ans[k])),涉及到取模，用到了乘法逆元.

设计状态的时候想清楚当前点有哪几种状态，它们对答案有没有影响.转移的时候想想转移过来的子节点必须满足什么要求，其它的点该怎么分配.求方案数的时候要分清楚是乘法原理还是加法原理.

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = , mod = ;

typedef long long ll;

int T, P, n, head[maxn], to[maxn * ], nextt[maxn * ], tot = ;

ll f[maxn][], g[maxn][], ans[maxn];

void add(int x, int y)

{

    to[tot] = y;

    nextt[tot] = head[x];

    head[x] = tot++;

}

ll qpow(ll a, ll b)

{

    ll res = ;

    while (b)

    {

        if (b & )

            res = (res * a) % mod;

        a = (a * a) % mod;

        b >>= ;

    }

    return res;

}

void dfs(int x, int fa)

{

    f[x][] = f[x][] = ans[x] = ;

    g[x][] = g[x][] = ;

    bool flag = false;

    ll sum = , mul = ;

    for (int i = head[x]; i; i = nextt[i])

    {

        int v = to[i];

        if (v != fa)

        {

            dfs(v, x);

            sum += max(f[v][], f[v][]);

            sum %= mod;

            f[x][] += max(f[v][], f[v][]);

            f[x][] %= mod;

            g[x][] = g[x][] * ans[v] % mod;

            mul = mul * ans[v] % mod;

            flag = true;

        }

    }

    if (!flag)

        g[x][] = ;

    for (int i = head[x]; i; i = nextt[i])

    {

        int v = to[i];

        if (v != fa)

        {

            if (f[x][] < f[v][] +  + sum - max(f[v][], f[v][]))

            {

                f[x][] = (((f[v][] +  + sum) % mod) - max(f[v][], f[v][]) + mod) % mod;

                g[x][] = g[v][] * mul % mod * qpow(ans[v],mod - ) % mod;

            }

            else

                if (f[x][] == f[v][] +  + sum - max(f[v][], f[v][]))

                    g[x][] = (g[x][] + g[v][] * mul % mod * qpow(ans[v],mod - ) % mod) % mod;

        }

    }

    if (f[x][] > f[x][])

        ans[x] = g[x][];

    if (f[x][] < f[x][])

        ans[x] = g[x][];

    if (f[x][] == f[x][])

        ans[x] = g[x][] + g[x][];

    ans[x] %= mod;

}

int main()

{

    scanf("%d%d", &T, &P);

    while (T--)

    {

        memset(head, , sizeof(head));

        tot = ;

        scanf("%d", &n);

        for (int i = ; i < n; i++)

        {

            int u, v;

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

            add(u, v);

            add(v, u);

        }

        dfs(, );

        printf("%lld ", max(f[][], f[][]));

        if (P == )

            printf("%lld", ans[] % mod);

        printf("\n");

    }

return ;

}

巴特西

noip模拟赛 hungary

最新文章

热门文章