我们可以树形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 ;
}

最新文章

  1. 三分钟玩转jQuery.noConflict()
  2. VC++6.0MFC运行的简单流程
  3. 【Spring】Junit加载Spring容器作单元测试
  4. SQL总结(四)编辑类
  5. 关于js的call()和apply()两个函数的一点个人看法
  6. RIA+REST架构实现完美WEB开发
  7. jquery几个常用的demo
  8. The solution for &quot;Eclipse is running in a JRE, but a JDK is required&quot;
  9. Microsoft Build 2016 Day 2
  10. [Solution] JZOJ-5818 做运动
  11. Java基础IO流(四)序列化与反序列化
  12. Python常用模块之json模块
  13. JavaScript形而上的策略模式
  14. 关于Ubuntu拒绝root用户ssh远程登录
  15. @Pointcut的用法
  16. KNN识别手写数字
  17. 认识loadrunner及相关性能参数
  18. 【开源推荐】PredictionIO:构建预测功能的机器学习服务器
  19. AABB和平面的相交性检测
  20. 20181113-7 Beta阶段第1周/共2周 Scrum立会报告+燃尽图 05

热门文章

  1. 优秀的Markdown编辑器MarkdownPad2免费版使用全功能
  2. NS_ASSUME_NONNULL_BEGIN,NS_ASSUME_NONNULL_END
  3. BSGS模版 a^x=b ( mod c)
  4. CSS笔记(三)背景
  5. 删除List中制定的值的方法
  6. iOS - OC NSSize 尺寸
  7. iOS - UIView
  8. SAP 批量查看凭证更改记录
  9. shiro-web整合
  10. [转载] 高流量大并发Linux TCP 性能调优