BZOJ-3696: 化合物

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;
}