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 ;

 }