ACM模版

描述

题解

很明显的树归问题,但是状态如何转移帮不好想,第一次见到这个题是我刚开始做 51Nod 时候的一场算法马拉松,很明显,那时候我并不会做,也不知道什么叫做树归,就一直没有再碰过了。今天看到这个题忽然想起来了,但是依然不知道具体怎么转移,先给一下官方题解吧……

感觉这个转移很套路,其实可以理解为,在合并两个块儿时,左边块儿的贡献变为了右边块儿结点数的 2 次幂,但是不考虑两个块儿之间的贡献,反之亦然,当然,最后我们还要考虑两个块儿之间的连通贡献,自然就是用到彼此的 sum[] 来乘喽……说句实在话,总是感觉这个题的问法儿有问题,按我的理解,期望不是应该是所有情况的平均效益吗?可是这个答案比没有城市被炸毁的效益还高,应该不叫做期望吧???还是说,我期望理解的有问题???

代码

#include <cstdio>

const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;

int n;
int idx;
int head[MAXN];
long long ans[MAXN];
long long sum[MAXN];
long long siz[MAXN];
long long pow_2[MAXN];

struct Edge
{
    int to, next;
} edges[MAXN << 1];

void addEdge(int u, int v)
{
    ++idx;
    edges[idx].to = v;
    edges[idx].next = head[u];
    head[u] = idx;
}

void dfs(int rt, int pre)
{
    sum[rt] = siz[rt] = 1LL;
    ans[rt] = 0LL;
    for (int i = head[rt]; i; i = edges[i].next)
    {
        int v = edges[i].to;
        if (v != pre)
        {
            dfs(v, rt);
            ans[rt] = ((ans[rt] * pow_2[siz[v]]) % MOD
                     + (ans[v] * pow_2[siz[rt]]) % MOD
                      + sum[rt] * sum[v] % MOD) % MOD;
            sum[rt] = (sum[rt] * pow_2[siz[v]] % MOD
                     + sum[v] * pow_2[siz[rt] - 1] % MOD) % MOD;
            siz[rt] = (siz[rt] + siz[v]) % MOD;
        }
    }
}

void init()
{
    pow_2[0] = 1;
    for (int i = 1; i < MAXN; i++)
    {
        pow_2[i] = (pow_2[i - 1] << 1) % MOD;
    }
}

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

int main()
{
    init();

    scanf("%d", &n);

    int x, y;
    for (int i = 1; i < n; i++)
    {
        scan_d(x), scan_d(y);
        addEdge(x, y);
        addEdge(y, x);
    }
    dfs(1, 0);

    printf("%lld\n", ans[1]);

    return 0;
}