有棵树,一开始节点上有01的权值。
每次可以缩一条边,两个点点权合并为其(NAND)和(先取and再取not)。
统计最终能缩成一个权值为1的点的方案数。答案对2取模。
(nle 300)(其实能做(nle 5000),甚至也许可以(O(n))?)
神仙题。
先考虑(n)为奇数的情况。
观察1:把操作按顺序两个两个分为一组。如果存在某组内操作的边不相邻,那么这个操作无贡献。
如果存在,建立双射:把第一个操作的边不相邻的组操作的两条边交换顺序。
两者答案相同,因为对(2)取模所以抵消。
观察2:一组中的操作(x o y o z)(即变成(NAND(NAND(x,y),z))),可以视作(x)吃掉了后面两个点(即操作过后变成(x))
打出(NAND(NAND(x,y),z))的真值表,发现结果不等于(x)的时候,(x=z)。
于是这和(z o y o x)结果一样,因为对2取模所以抵消,因此假装结果变成了(x)也没有问题。
结合观察1和观察2,问题变成每次选择个(x o y o z),然后(x)吃掉后面两个点。
观察3:令最后一个留下的点为(rt)(结果是(rt)的权值)。每组操作一定要和(rt)有关。
如果第一次某组操作和(rt)无关,将这组顺序完全交换,得到结果完全一样。显然这也是个双射。
于是又抵消了。
于是做法是:枚举(rt),对除了(rt)的节点划分成若干组,每组为相邻的节点(就是匹配)。模拟剥叶子可知如果存在一组完美匹配,匹配唯一。然后将各匹配缩点,新树的合法遍历顺序(每个点遍历前要先遍历父亲)个数就是答案。
时间(O(n^2))。
现在考虑(n)为偶数。naive的做法是直接枚举第一次操作的边然后变成奇数的问题,时间(O(n^3))反正能过原题。
观察4:第一次操作的边缩点之后一定作为(rt)统计答案。
如果第一次操作的边不作为(rt)。先给边缩点,从此时的(rt)开始做个上面奇数情况的算法,搞出了个唯一的匹配。(如果能找到得到话)
找到这个边缩点所在的匹配。匹配大概长成([(x- y)- z])或([x- (y- z)]),小括号表示边缩点。
发现将([(x- y)- z])换成([x- (y- z)])(或反之),结果相同,并形成了双射。
(就是说一开始缩的边为(x-y),根为(rt),变成一开始缩的边为(y-z),根为(rt))
形成双射:一开始缩(x-y)的情况已经形成了合法的匹配。因为两种方案中匹配唯一,并且这样变换过后,除了(x,y,z)之外匹配保持不变,所以一开始缩(y-z)也是合法的匹配。并且两种方案中(x,y,z)都是在同一个匹配里的,于是可以双射。
于是枚举第一个缩的边,将其作为(rt),后面类似于奇数的做法,就可以(O(n^2))啦!
最后想想,枚举根,划分唯一匹配,算遍历数,是不是能换根啊……
也许能(O(n))啦。
using namespace std;
#include <bits/stdc++.h>
const int N=305;
int n;
struct EDGE{
int to;
EDGE *las;
};
struct Graph{
EDGE e[N*2];
int ne;
EDGE *last[N];
void link(int u,int v){
e[ne]={v,last[u]};
last[u]=e+ne++;
}
void clear(){
ne=0;
memset(last,0,sizeof(EDGE*)*(n+1));
}
} G,F;
int c[N];
int C[N][N];
int sz[N],cov[N];
int predfs(int x,int fa){
for (EDGE *ei=G.last[x];ei;ei=ei->las)
if (ei->to!=fa){
int t=predfs(ei->to,x);
if (!t)
return 0;
}
if (!cov[x]){
if (cov[fa])
return 0;
cov[x]=cov[fa]=x;
}
for (EDGE *ei=G.last[x];ei;ei=ei->las)
if (ei->to!=fa && cov[ei->to]!=cov[x])
F.link(cov[x],cov[ei->to]);
return 1;
}
int calc(int x,int fa){
sz[x]=0;
int pro=1;
for (EDGE *ei=F.last[x];ei;ei=ei->las){
pro=pro*calc(ei->to,x);
sz[x]+=sz[ei->to];
pro=pro*C[sz[x]][sz[ei->to]];
}
sz[x]++;
return pro;
}
int main(){
//freopen("in.txt","r",stdin);
scanf("%d",&n);
for (int i=1;i<n;++i){
int u,v;
scanf("%d%d",&u,&v);
G.link(u,v),G.link(v,u);
}
for (int i=1;i<=n;++i)
scanf("%d",&c[i]);
C[0][0]=1;
for (int i=1;i<=n;++i){
C[i][0]=1;
for (int j=1;j<=i;++j)
C[i][j]=C[i-1][j-1]^C[i-1][j];
}
int ans=0;
if (n&1){
for (int x=1;x<=n;++x){
F.clear();
memset(cov,0,sizeof(int)*(n+1));
if (!predfs(x,0))
continue;
ans^=calc(x,0)*c[x];
}
}
else{
for (int x=1;x<=n;++x)
for (EDGE *ei=G.last[x];ei;ei=ei->las){
int y=ei->to;
if (x<y){
F.clear();
memset(cov,0,sizeof(int)*(n+1));
cov[x]=cov[y]=y;
if (!predfs(x,0))
continue;
int c_=!(c[x]&&c[y]);
ans^=calc(y,0)*c_;
}
}
}
printf("%d
",ans);
return 0;
}