背景

　　“西瓜是可以种在平行世界的！”——小鸟游六花

描述

　　又到了收获时节，为了方便采摘，六花酱现在要给众西瓜命名，她已经为每个西瓜想好了一个名字，名字一共有m个属性，一个名字是否拥有这些属性可以用一个长度为m的01串xi来表示，表示这个名字是否吉利，是否好听等等。

　　她可以在任意时刻把这个名字倒过来（就像题目名字），倒过来后，原来好听的就不好听了，原来不好听的就好听了。即把这个01串取反。

　　每个属性都有一个价值vi，一个西瓜的价值为把它的名字拥有的所有属性的价值加起来。即第i个名字的价值为。其中x_i,k表示第i个名字是否拥有第k个属性，0表示没有，1表示有。

当她手上拥有一堆西瓜时，这堆西瓜拥有第i个属性当且仅当存在一个西瓜拥有这一个属性，然后计算出的价值就是这堆西瓜的价值。即把所有西瓜的名字01串或起来之后当成一个西瓜处理。

　　现在六花开始采摘西瓜。瓜地构成一棵n个节点的树，一个点上有一个西瓜。她从根（1号节点）开始走，每次只能往儿子方向走。走到一个点时，她可以把这个西瓜采摘起来，每摘到一个西瓜，她可以把手头所有西瓜名字任意修改（修改即把名字倒过来）。

每个点会有一个价值，这个价值是她从根走到这个点，手上这堆西瓜价值的最大值（允许对西瓜们改名后的最大值）。一圈西瓜摘完，每个点的价值都已经确定。

　　摘完西瓜闲来无事，六花开始在西瓜地里漫步，她可以从任意点出发，在任意点结束（没有只能往儿子方向走的限制）。她不希望自己走过的相邻两个点的价值相同，同时不希望走过重复的点。她想知道，对于每个d，自己能走出的长度为d路径一共有多少条。这里的路径长度定义为路径上点的数量。

输入格式

　　第一行两个整数n,m。表示西瓜的个数（树的节点数量），属性的数量。

　　接下来n行，每行一个长度为m的01串，第i行的01串描述一个第i个西瓜的名字。

　　第n+2行包含m个正整数，第i个数vi表示第i个属性的价值。

　　再有n-1行，每行一个1到n中的整数，第i行的整数fa_i表示树中i+1号节点的父节点。

输出格式

　　如果能走出最大的路径长度为D，则输出D个整数，第i个数表示长度为i的路径数量。

样例输入

5 20

10110000001010011111

10010001110111101111

11111111111111111111

10000110011111110111

10110000001010011111

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1

1

2

3

样例输出

5 3 2 1

数据范围与约定

　　对于初： 1<= n<= 10,1<= m<= 20,1<= v_i<= 10⁹

　　对于续： 1<= n<= 10⁵,1<= m<= 200,1<= v_i<= 10⁹，保证不存在节点的价值达到理论最大值，且树的深度不超过10。

　　对于终： 1<= n<= 10⁵,1<= m<= 200,1<= v_i<= 10⁹

样例解释

　　1号点价值为10

　　2号点价值为17（1号西瓜名字倒过来，2号不变）

　　3号点价值为20

　　4号点价值为19（三个西瓜均不变即可）

　　5号点价值为20

　　长度为1的路径为5点单独一条路径

　　长度为2的路径为：4->2，2->1，1->3

　　长度为3的路径为：4->2->1，2->1->3

长度为4的路径为：4->2->1->3

备注

本题输入数据较多，请使用stdio.h读入。实测0.7s时限下，stdio.h+scanf需要的最大用时约0.4s。

—————————————————————————————————————————————

这道题 首先深度大于logm的点肯定能达到最大值。因为每次我们可以把至少一半的为0的属性变成1。

这个证明一下把

————————————————————————————————————————————————

因为我们考虑当前拥有的西瓜为x 要摘的西瓜为y

我们按二进制位考虑 因为x反转和y反转没有区别

考虑反转y 那么x是1的位不用考虑 剩下的0位 如果和y或起来不足一半 就反转y这样就大于一半了

————————————————————————————————————————————————

然后未到达最大值的点相邻两个肯定价值不同，也就是说路径相邻两个值不同的限制其实是把达到最大值的子树（不包括他本身）砍掉。

所以题目给的价值是没有用的 父亲和儿子只要不是全为0就不可能相同

这样我们只要考虑到每个点是否全为0就好了

我们发现 根到当前点 几个串可以组成一个矩阵

矩阵的行表示组成每个点的串 那么只要每一列都能有个1就能全0了

可是怎么判断一个矩阵能否达到上述状态呢

我们可以从亦或的角度考虑 反转一个序列就是整行异或1

那么问题就变成了找一个和列一样长的01串 使他和每一列异或后实现每一列都有1

那么由异或的性质得 A&A=0

所以如果所有列的排列（即不同的列数）达到2^k（k是到当前点收集到的点数） 那么所有的排列都在矩阵中了

所以不论你选什么 必然有一列为0 反之你随机选一个不在矩阵中存在的排列就可以了 QAQ

最后问题就转换成了求树上长度为d的路径的数量 然后我们考虑每一个点 算经过他的路径

就是一波树形dp了 233333

#include<stdio.h>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int M=1e5+7;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<‘0‘||c>‘9‘){if(c==‘-‘) f=-1; c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){ans=ans*10+(c-‘0‘); c=getchar();}
    return ans*f;
}
int n,m,k;
char s[255];
int cnt,first[M],f[M][257];
int usd[2507],h[M];
LL ans[55],dis[M][55];
struct node{int to,next;}e[M];
void ins(int a,int b){e[++cnt]=(node){b,first[a]}; first[a]=cnt;}
void dfs(int x,int d){
    //printf("(%dL)",x);
    cnt=1<<d+1;
    for(int i=0;i<m;i++){
        if(f[x][i]) h[i]|=(1<<d);
        if(usd[h[i]]!=x) cnt--,usd[h[i]]=x;
    }
    if(cnt) first[x]=0;
    for(int i=first[x];i;i=e[i].next) dfs(e[i].to,d+1);
    for(int i=0;i<m;i++) h[i]&=~(1<<d);
    //printf("(%dR)",x);
}
void dp(int x,int d){
    ++dis[x][d];
    for(int i=first[x];i;i=e[i].next){
        int now=e[i].to;
        dp(now,d+1);
        for(int p=d;p<10;p++)
         for(int q=d;q<10;q++) ans[p+q-2*d]+=1LL*dis[x][p]*dis[now][q];
        for(int p=0;p<10;p++) dis[x][p]+=dis[now][p];
    } 
}
int main(){
    n=read(); m=read();
    for(int i=1;i<=n;i++){
        scanf("%s",s);
        for(int j=0;j<m;j++) f[i][j]=s[j]==‘1‘;
    }
    for(int i=1;i<=m;i++) read();
    for(int i=2;i<=n;i++) k=read(),ins(k,i);
    dfs(1,0);
    dp(1,0);
    k=25;
    ans[0]=n;
    while(!ans[k]) k--;
    for(int i=0;i<=k;i++) printf("%lld ",ans[i]); 
    return 0;
}

View Code

花六游鸟小