BZOJ3696 化合物

时间:2023-03-10 02:21:32
BZOJ3696 化合物

我们可以树形dp...

令f[p][d]表示以p为根的子树,与p距离为d的结点数

然后我们计算答案:

一种是从某个节点q到根p的方案,对和为d的贡献是1

另一种是p的一个子树中的节点x到另一个子树中的节点y的方案,对和为d[x] ^ d[y]的贡献为1

第二种我们可以通过f暴力求出,话说什么时候去研究一下FWT啊。。。

 /**************************************************************
Problem: 3696
User: rausen
Language: C++
Result: Accepted
Time:476 ms
Memory:207460 kb
****************************************************************/ #include <cstdio>
#include <algorithm> using namespace std;
const int N = 1e5 + ;
const int H = ; struct edge {
int next, to;
edge() {}
edge(int _n, int _t) : next(_n), to(_t) {}
} e[N]; int n;
int first[N], tot;
int f[N][H], ans[H], dep[N]; inline int read() {
int x = , sgn = ;
char ch = getchar();
while (ch < '' || '' < ch) {
if (ch == '-') sgn = -;
ch = getchar();
}
while ('' <= ch && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return sgn * x;
} inline void Add_Edge(int x, int y) {
e[++tot] = edge(first[x], y), first[x] = tot;
} #define y e[x].to
void dfs(int p) {
int x, i, j;
f[p][] = ;
for (x = first[p]; x; x = e[x].next) {
dfs(y);
for (i = ; i <= dep[p]; ++i)
for (j = ; j <= dep[y]; ++j)
ans[i ^ (j + )] += f[p][i] * f[y][j];
dep[p] = max(dep[p], dep[y] + );
for (i = ; i <= dep[y]; ++i)
f[p][i + ] += f[y][i];
}
}
#undef y int main() {
int i, mx;
n = read();
for (i = ; i <= n; ++i)
Add_Edge(read(), i);
dfs();
for (mx = H - ; mx; --mx)
if (ans[mx]) break;
for (i = ; i <= mx; ++i)
printf("%d\n", ans[i]);
return ;
}