标签：树形DP
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
Sample Output
1
2
HINT
【数据规模与约定】
用h表示树结构分子的最大深度。
N<=10^5,H<=500
题意：给定一棵树，问有多少对节点（u，v）满足dis(lca(u,v),u) ^ dis(lca(u,v),v)==k
分析：70分n<=3000的暴力很好写
正解应该也算暴力吧，枚举每个点和深度，设a[x][i]表示以x为根节点的子树中深度为i的节点个数，直接计算点对数量
Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define LL long long
#define reg(x) for(int i=head[x];i;i=e[i].next)
using namespace std;
inline LL read()
{
LL f=1,x=0;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;
}
const LL maxn=1e5+6;
LL a[maxn][1<<9],ans[1<<9],head[maxn],deep[maxn],n,cnt=0;
struct edge{LL to,next;}e[maxn<<1];
void dfs(int x)
{
a[x][0]=1;
reg(x){
dfs(e[i].to);
rep(j,0,deep[x])
rep(k,0,deep[e[i].to])ans[j^(k+1)]+=a[x][j]*a[e[i].to][k];
deep[x]=max(deep[x],deep[e[i].to]+1);
rep(j,0,deep[x])a[x][j+1]+=a[e[i].to][j];
}
}
int main()
{
n=read();
rep(i,2,n){LL x=read();e[++cnt]=(edge){i,head[x]},head[x]=cnt;}
dfs(1);
LL mx=1<<9,t;
dep(i,mx,1)if(ans[i]){t=i;break;}
rep(i,0,t)printf("%lld\n",ans[i]);
return 0;
}
本文可以转载，但必须附上原文链接，否则你会终生找不到妹子！！！欢迎关注我的CSDN: ahyjjr
