[文章目录]
Description
这个分子构成一个树结构，1号分子为根。 若两个原子i、j到它们的最近公共祖先的距离分别是Li和Lj，定义它们的Aij值为：Aij=Li xor Lj 题目要求对于每一个k(k∈N)，求出两两A值为k的原子对个数。
不知道为什么，自带十倍常数。。。另外岷县跑不过的时间复杂度居然还是正解。。。
树形dp，num[x][i]表示以x为根长度为i的链的个数。然后每次暴力h方扫，另外将循环至循环到最深的节点的深度。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,num[100010][510],ans[1024];
int head[101000],to[101000],nxt[101000],cnt;
void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
int dfs(int x)
{
int i,j,k,mx=0; num[x][0]=1;
for(i=head[x];i;i=nxt[i])
{
int tmp=dfs(to[i])+1; mx=max(mx,tmp);
for(j=1;j<=tmp;++j)
for(k=0;k<=mx;++k)
ans[k^j]+=num[x][k]*num[to[i]][j-1];
for(j=1;j<=tmp;++j) num[x][j]+=num[to[i]][j-1];
}
return mx;
}
int main()
{
scanf("%d",&n); int i,x;
for(i=2;i<=n;++i)
{
scanf("%d",&x);
add(x,i);
}
dfs(1); int now;
for(i=512;i>=0;i--) if(ans[i]){ now=i; break; }
for(i=0;i<=now;++i) printf("%d\n",ans[i]);
return 0;
}