首页 > 代码库 > bzoj3696 化合物
bzoj3696 化合物
Description
首长NOI惨跪，于是去念文化课了。现在，他面对一道化学题。
这题的来源是因为在一个奇怪的学校两个化竞党在玩一个奇怪的博弈论游戏。这个游戏很蛋疼，我相信你们也没有兴趣听。
由于这个游戏涉及博弈论，因此化竞的同学就要求首长求一个类似SG函数的值。
他们手中有一种非常神奇的化合物，它的分子由N个原子组成（不要在意一个原子可能和及其多个原子成键这个细节）。这个分子构成一个树结构，1号分子为根。 若两个原子i、j到它们的最近公共祖先的距离分别是Li和Lj，定义它们的Aij值为：
Aij=Li xor Lj
题目要求对于每一个k(k∈N)，求出两两A值为k的原子对个数。
Input
第一行一个整数N。
接下来N-1行，每行一个整数p，第新亍的整数表示第i个原子的父亲为p。
Output
从K=0开始，第k+1行输出两两A值为K的原子对个数，输出到第一个不为零的数为止。
Sample Input
3
1
1
1
1
Sample Output
1
2
2
HINT
【数据规模与约定】
用h表示树结构分子的最大深度。
N<=10^5,H<=500
h才500……这不是随便搞么
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define pi 3.1415926535897932384626433832795028841971using namespace std;inline LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}inline void write(LL a){ if (a<0){printf("-");a=-a;} if (a>=10)write(a/10); putchar(a%10+‘0‘);}inline void writeln(LL a){write(a);printf("\n");}struct edge{ int to,next;}e[100010];int n,cnt;int head[100010];int fa[100010];int dep[100010];int son[100010][510];int ans[512];inline void insert(int u,int v){ e[++cnt].to=v; e[cnt].next=head[u]; head[u]=cnt;}inline void dfs(int x){ son[x][0]++; for (int i=head[x];i;i=e[i].next) { dfs(e[i].to); for (int j=0;j<=dep[x];j++) for (int k=0;k<=dep[e[i].to];k++) ans[j^(k+1)]+=son[x][j]*son[e[i].to][k]; dep[x]=max(dep[x],dep[e[i].to]+1); for(int j=0;j<=dep[e[i].to];j++) son[x][j+1]+=son[e[i].to][j]; }}int main(){ n=read(); for (int i=2;i<=n;i++) fa[i]=read(),insert(fa[i],i); dfs(1); int mx=511; while (!ans[mx])mx--; for (int i=0;i<=mx;i++)printf("%d\n",ans[i]); return 0;}
bzoj3696 化合物
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。