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