BZOJ 3696 - 化合物 | Sengxian's Blog

BZOJ 3696 - 化合物

#动态规划 #树形动态规划

Published on 2016-04-09

描述

首长NOI惨跪，于是去念文化课了。现在，他面对一道化学题。
这题的来源是因为在一个奇怪的学校两个化竞党在玩一个奇怪的博弈论游戏。这个游戏很蛋疼，我相信你们也没有兴趣听。
由于这个游戏涉及博弈论，因此化竞的同学就要求首长求一个类似SG函数的值。
他们手中有一种非常神奇的化合物，它的分子由 $N$ 个原子组成（不要在意一个原子可能和及其多个原子成键这个细节）。这个分子构成一个树结构， $1$ 号分子为根。若两个原子 $i$ 、 $j$ 到它们的最近公共祖先的距离分别是 $L_i$ 和 $L_j$ ，定义它们的 $A_{i,j}$ 值为：

A_{i,j}=L_i\;\mathrm{xor}\;L_j

题目要求对于每一个 $k(k\in N)$ ，求出两两 $A$ 值为 $k$ 的原子对个数。

样例输入

3
1
1

样例输出

1
2

分析

注意到枚举两个点，求 LCA 绝对是爆炸的。所以我们从 LCA 统计答案，显然对于一个节点， $u$ 的不同子树中的任意两个节点的 LCA 都是 $u$ ，利用这个性质我们考虑树形 DP。
设 $dp[i][j]$ 为在 $i$ 及其子树中，与节点 $i$ 距离 $j$ 的节点个数。
显然 $dp[i][0] = 1$ ，还有 $dp[i][j + 1] = \sum\limits_{v\in \text{sons}}dp[v][j]$ 。
考虑如何统计答案，对于节点 $u$ ，顺次遍历其子树，记录 $f[i][j]$ 考虑 $u$ 以及前 $i$ 个儿子及其子树中距离为 $j$ 的个数，那么对于新遍历的子树只需分别枚举距离即可。
看上去比较麻烦，代码实现比较简单，因为 $f$ 和 $dp$ 是可以同时统计的。

代码

//  Created by Sengxian on 4/9/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 3696 树形DP
#include <algorithm>
#include <iostream>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;

inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 100000 + 3, maxh = 500 + 3;
int mx[maxn], f[maxn][maxh], ans[maxn], n;
vector<int> G[maxn];

void dfs(int u) {
    f[u][0] = 1;
    for (int i = 0; i < G[u].size(); ++i) {
        int v = G[u][i];
        dfs(v);
        for (int j = 0; j <= mx[u]; ++j)
            for (int k = 0; k <= mx[v]; ++k)
                ans[j ^ (k + 1)] += f[u][j] * f[v][k]; //统计答案
        mx[u] = max(mx[u], mx[v] + 1);
        for (int j = 0; j <= mx[v]; ++j)
            f[u][j + 1] += f[v][j]; //从子树的信息更新自己
    }
}

int main() {
    n = ReadInt();
    for (int i = 1; i < n; ++i) {
        int f = ReadInt() - 1; 
        G[f].push_back(i);
    }
    dfs(0);
    for (int i = 0; i < n; ++i) {
        if (ans[i] == 0) break;
        printf("%d\n", ans[i]);
    }
    return 0;
}

BZOJ 1827 - [Usaco2010 Mar]gather 奶牛大集会 BZOJ 2324 - [ZJOI2011]营救皮卡丘