众所周知bzoj3914是一道没什么人愿意写的码农题

今天闲的没事想写一写传说中的基于LCT的树上同色连通块维护算法，然后写到一半发现自己看不懂怎样expose才能维持主树和辅树的性质……

所以说有没有哪位dalao愿意简单讲几句……或者讲一下另一种做法也行

（只要不用ETT，代码长度什么的就都无所谓了

（ps：用LCT套堆维护直径就可以省去维护括号序做法中的ETT了

QAQ 经历了高三一年的百炼成废铁钢，终于能有空摸一摸键盘辣

看了看以前自己写的博客才发现自己好多东西都忘掉了……

所以准备刷题+重写以前的题目来恢复一下塑料组（意思是还不如青铜组）的水平

鉴于上海某大学日程安排还算宽松，下午可以自由刷题，那就每天下午准时就位吧。

我会把AC掉的题目的简要题解发上来。

Hell, it's about time.

——Tychus J. Findlay

Wed. 6.13

COGS2479 偏序 裸的分治套分治。

COGS1481 最大公约数之和 线性筛&基础数论复习。

[NOI2010]超级钢琴 区间裂解（其实只是在复习ST表

LOJ6197 法克 复习复习Dinic板子和网络流理论（自己出的题还要看题解才会做系列

[AHOI2013]作业 莫队+对权值分块（主要是复习莫队板子

（emmm我怎么感觉今天写的都是一些自己本来不用复习都会的东西

Thu. 6.14

emmm先挖几个坑慢慢填……

UPD：

上午考试爆炸辣……果然这才是我的真实水平2333333（雾

下午好好刷刷题吧……

没填的：

LOJ6207 米缇 （杜教筛+牛顿插值）

COGS2354 疯狂的字符串 （学长搬的论文题，很神的FFT）

已经填了的：

COGS2340 疯狂的求和问题 （又是学长搬的板子题）牛顿插值的FFT实现。

LOJ104 普通平衡树 （原题来自Tyvj） 麻麻我终于又学会写Treap辣！（雾

6.18 UPD：

前两天放假，出去浪了2333333……中断了几天，明天继续吧QwQ

Tue. 6.19

emmm我打算出一套题来着……正在写题面和标程。

下午忙着写题面去了（摊手）……所以今天并没有过几道题……

51Nod12363 序列求和V3 代入Fibonacci数列通项，二项式定理化简之后快速幂即可

51Nod1829 函数 我说这是裸的斯特林数你信么……（摊手

Wed. 6.20

bzoj2002 Bounce弹飞绵羊 一个LCT板子都要调一个多小时，真是老了……

Thu.6.21

51Nod1237 最大公约数之和V3 复习一波杜教筛板子。

NOI2015 软件包管理器 链剖大板子都调这么半天我是智障QAQ……

Sat. 6.23

昨天高考出分，熬夜等分去了，看见分了睡不着，今天好困……

COGS2243 两个傻逼错误调了三小时QAQAQAQ……（别看这题叫Toptree，其实只是LCT维护子树信息

Sun. 6.24

COGS2608 无根树 链剖维护动态树形DP。

51Nod1678 lyk与gcd $10^5$以内的数最多只有$6$个质因子，所以大力容斥就好了。

Wed. 6.27

前两天忘了更了……（捂脸

算了不补了就这样吧（逃

bzoj3339 Rmq Problem 莫队分块大法好（这种题还交了四遍才过，我是智障QAQ……

bzoj5090 [Lydsy1711月赛]组题 不知道正解是啥，我是用的分数规划的套路，大力迭代跑过去了，跑得还挺快……

（UPD：看了看各路dalao的题解，发现大都是二分答案233333……看来我还有救

bzoij4815 小Q的表格 做过的题还交这么多遍才过，我是智障QAQ……

Thu. 6.28

MDZZ，写一道字符串真tm难……

HackerRank Special Substrings 后缀自动机+回文树+set，不说了我想静静……

Fri. 6.29

今天放假233333333

LOJ2033 [SDOI2016]生成魔咒 复习一下后缀自动机板子。

LOJ6198 谢特 后缀自动机+Trie，连应该对反串建后缀自动机都忘了我是智障QAQ……

有一天自己想FWT的时候冒出来的问题

FWT_or实际上在干这样的事情

$$FWT(f)(S)=\sum_{T\subset S}f(T)$$

如果把求和换成min也是可以的

同时如果要求

$$h(S)=\sum_{T\subset S}f(T)g(S-T)$$

的话也不难搞

那么问题来了，如果要求

$$h(S)=\min_{T\subset S}\{f(T)+g(S-T)\}$$

呢？QAQ

UPD：

博主制杖了……似乎

$$h(S)=\sum_{T\subset S}f(T)g(S-T)$$

也不好弄的样子……

还有几天就是NOI了，还有5个晚上可以在学校做题，这5个晚上我决定好好练习一下平常没怎么注意过的提答题，为NOI做准备。

计划每天晚上做一道题（为什么昨天没有呢？因为太颓了），为了防止自己偷懒，每做完一道题我会在这里发（我拿到的分的）伪题解。

同时为了防止偷懒，提前列好计划：

• 7.12 UOJ#208 UOIP十合一
• 7.13 UOJ#215 【UNR #1】果冻运输
• 7.14 UOJ#109 【APIO2013】TASKSAUTHOR
• 7.15 UOJ#190 【集训队互测2016】消失的源代码
• 7.16 #135. 【UR #9】包子晚宴

（后两道题还要感谢 @bzoj 的提醒）

（7.17和7.18的话……留出来敲板子和复习好了……）

7.12 UOJ#208 UOIP十合一

我的最后提交

我还是Naive……测试点6想到了答案就是$n$个点的有标号DAG个数，然而并没有记住$O(n^2)$的递推式怎么玩……不过要我手推$O(n^3)$的递推式的话还是不难的……

感觉新发一篇博客可能有点占UOJ博客的版面，那我还是都写在这里好了……

（感觉贴代码有点占地方，毕竟这里还要写好几天……所以就不贴代码了）

测试点1

一眼看去感觉像是出点编号$\le$入点编号，判了一发发现的确是对的，去掉自环就好了……

测试点2

观察一波之后感觉比较有规律，写个程序判一下发现每个弱连通块都正好有5个点10条边，那么对每个连通块分别暴力就行了。

测试点3

不难发现每个点恰有一条出边，那么找出所有的环之后对每个连通块减去选环的方案数再乘起来就行了……

测试点4

这个……因为一眼看着感觉没什么规律，就没往分层图上想……

我还是Naive了啊……第二次被分层图坑了……（上一次是UOJ#259 子集计数问题）

测试点5

一眼看上去也没啥规律，不过反正我在做测试点2的时候写了一个Tarjan，直接搬过来判一下发现每个SCC的边数都很少，那么对每个SCC暴力之后乘起来，最后乘上不属于SCC内部的边的贡献就行了。

测试点6

一眼看过去发现是一个$n=100$的完全图，但是一开始NC了，没发现答案就是$n$个点的有标号DAG个数……不过瞎xx暴力了前几项之后发现一个熟悉的数字：543……这个数好像在我写DAG计数的时候见过，那看来答案就是$n$个点的有标号DAG个数了。

然而我是在最后才想起来答案就是这个的，并没有时间再写$O(n^3)$的DP了……有点可惜。

（设$f_{i,j}$表示$i$个点且有$j$个点入度为0的DAG个数，转移的时候瞎xx搞一搞就能搞出$O(n)$的转移了）

测试点7~10

……后4个测试点以我现在的能力是做不出来的……（我没写过测试点7这种类型的子集DP……）

所以……略吧（逃

总结

其实前6个测试点对我来说都是很可做的范围的……然而最后只拿到了40分，看来自己提答经验还是不够，并且做的实在太慢了。

没关系，今晚上还有UOJ#215 【UNR #1】果冻运输，再接再厉……

ps：一会儿还要去UNR……

7.13 UOJ#215 【UNR #1】果冻运输

我的最后提交

这题……有毒……

真的没啥可写的……我的分都是纯手玩……

玩了两个小时只玩出了40分……主要是因为没有直接看一遍所有数据，早知道都这么小我就去写暴搜了啊QAQ……

ps：这种考察选手玩游戏能力的题真的好吗QAQ……

7.14 UOJ#109 【APIO2013】TASKSAUTHOR

我的最后提交

因为某些事情耽误了一点时间，做题的时候心也不静，然后就33分滚粗了QAQ……

子任务1

想卡Floyd很简单嘛……造一个$101$个点没有边的图就行了，至于询问随便打一个即可。

子任务2

要让Bellman-Ford达到$(n-1)m$的上界很简单，反着造（正着造会因为循环顺序的原因一遍更新完）一个边权为$1$的链，其余边边权设成一个很大的数就行了。

为了不让Floyd TLE，最多只能有$100$个点……算了算发现边数需要$10^3$多一点，手动枚举一波边数就行了。

子任务3

……正常情况下子任务1的输出应该正好有$105$个整数，所以直接把子任务1的答案粘过来即可……

子任务5

……我还是Naive

直接把子任务2粘过来了，结果只有4分……后来才想起来因为前面是Dijkstra所以点数可以大一些……QAQ

子任务7

显然后面的问题必须恰好$71$个点和$1500$条边才能满分，随机了几个图发现暴搜都会TLE，随便交一个就好了……

（这个点是真·送分点）

总结

听说这个提答很简单啊……然而分还是这么低，不知道是因为心不静还是能力不够。

还有两道提答，再接再厉。

话说为什么没找到题解咧……算了我自己写一个好了……

由于弱菜AntiLeaf能力有限，部分测试点无法通过，见谅……

测试点1

一眼看见$n=24$，$k=8$，用Python算了算发现$n\choose k$才几十万，那直接暴力就好了。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=35;
bool a[maxn][maxn],b[maxn];
int n,m,k,p;
int main(){
    freopen("subset1.in","r",stdin);
    freopen("subset1.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&k,&p);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y]=a[y][x]=true;
    }
    for(int i=1;i<=k;i++)b[i]=true;
    next_permutation(b+1,b+n+1);
    int ans=0;
    do{
        bool ok=true;
        for(int i=1;i<=n;i++)if(b[i]){
            for(int j=i+1;j<=n;j++)if(b[j]&&a[i][j]){
                ok=false;
                break;
            }
        }
        if(ok)ans++;
    }while(next_permutation(b+1,b+n+1));
    printf("%d",ans%p);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

测试点2

$n=40$，$k=11$，看上去不太好搞……？

其实只要在暴搜的时候判一下加上这个点是否合法就行了……

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=55;
void dfs(int,int);
bool a[maxn][maxn];
int n,m,k,p,v[maxn],ans=0;
int main(){
    freopen("subset2.in","r",stdin);
    freopen("subset2.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&k,&p);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y]=a[y][x]=true;
    }
    dfs(1,0);
    printf("%d",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
void dfs(int x,int t){
    if(t==k){
        if(++ans==p)ans=0;
        return;
    }
    if(x==n+1)return;
    bool ok=true;
    for(int i=1;i<=t;i++)if(a[x][v[i]]){
        ok=false;
        break;
    }
    if(ok){
        v[t+1]=x;
        dfs(x+1,t+1);
    }
    dfs(x+1,t);
}

测试点3

$n=100$，$k=32$，看来暴搜没戏……

不过注意到$m=n-1$，猜想这是一棵树，仔细观察之后发现它确实是一棵树，那么跑一个树形DP即可：$f_{i,j,0/1}$表示$i$的子树中选了$j$个点，是否选了$i$的方案数，合并的时候搞一搞即可。

数据范围比较小，因此直接写$O(n^3)$的DP也可以过。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=105;
void dfs(int);
void add(int,int);
vector<int>G[maxn];
int n,m,k,p,f[maxn][maxn][2],g[maxn][2];
int main(){
    freopen("subset3.in","r",stdin);
    freopen("subset3.out","w",stdout);
    scanf("%d%*d%d%d",&n,&k,&p);printf("n=%d\n",n);
    for(int i=2,x;i<=n;i++){
        scanf("%d%*d",&x);
        G[x].push_back(i);
    }
    dfs(1);
    printf("%d",(f[1][k][0]+f[1][k][1])%p);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
void dfs(int x){
    f[x][0][0]=f[x][1][1]=1;
    for(int i=0;i<(int)G[x].size();i++){
        dfs(G[x][i]);
        add(x,G[x][i]);
    }
}
void add(int x,int y){
    memset(g,0,sizeof(g));
    for(int i=0;i<=n;i++)for(int j=0;i+j<=n;j++){
        g[i+j][0]=(g[i+j][0]+(long long)f[x][i][0]*(f[y][j][0]+f[y][j][1]))%p;
        g[i+j][1]=(g[i+j][1]+(long long)f[x][i][1]*f[y][j][0])%p;
    }
    memcpy(f[x],g,sizeof(g));
}

测试点4

不难发现这也是一棵树，那继续用上面的树形DP即可。

为了压内存，用vector开DP数组，同时在合并之后清空原数组即可。

（注释掉了的那些东西是为了防止被卡内存写的找直径后DP每个子树最后再DP序列的做法，然而好像写挂了，WA……换成直接DP就过了，浪费了我十分钟……并不知道直接暴力空间对不对，不过我跑的时候并没有费很多的内存）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=100005;
struct DP{
    vector<int>f[2];
    DP(){}
    void operator+=(DP&);
}f[maxn];
void bfs(int);
void dfs(int);
vector<int>G[maxn];
bool vis[maxn];
int n,k,mod,p[maxn],d[maxn],vec[maxn],q[maxn];
int main(){
    freopen("subset4.in","r",stdin);
    freopen("subset4.out","w",stdout);
    scanf("%d%*d%d%d",&n,&k,&mod);
    for(int i=1,x,y;i<n;i++){
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    /*bfs(1);
    int u=1;
    for(int i=1;i<=n;i++)if(d[i]>d[u])u=i;
    bfs(u);
    int v=1;
    for(int i=1;i<=n;i++)if(d[i]>d[v])v=i;
    bfs(v);
    int cnt=0;
    while(u){
        vec[++cnt]=u;
        vis[u]=true;
        u=p[u];
    }
    fprintf(stderr,"u=%d v=%d cnt=%d\n",vec[1],vec[cnt],cnt);
    for(int i=1;i<=cnt;i++){
        dfs(vec[i]);
        fprintf(stderr,"i=%d dfs(%d) OK\n",i,vec[i]);
    }fprintf(stderr,"OK...\n");
    DP ans=f[vec[1]];
    for(int i=2;i<=cnt;i++)ans+=f[vec[i]];
    printf("%d",(ans.f[0][k]+ans.f[1][k])%mod);*/
    dfs(1);
    printf("%d",(f[1].f[0][k]+f[1].f[1][k])%mod);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
void bfs(int x){
    int head=0,tail=0;
    q[tail++]=x;
    p[x]=d[x]=0;
    while(head!=tail){
        x=q[head++];
        for(int i=0;i<(int)G[x].size();i++)if(G[x][i]!=p[x]){
            p[G[x][i]]=x;
            d[G[x][i]]=d[x]+1;
            q[tail++]=G[x][i];
        }
    }
}
int cnt=0;
void dfs(int x){
    vis[x]=true;fprintf(stderr,"%d\n",++cnt);
    f[x].f[0].resize(2);
    f[x].f[1].resize(2);
    f[x].f[0][0]=f[x].f[1][1]=1;
    for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]]){
        dfs(G[x][i]);
        f[x]+=f[G[x][i]];
    }
}
#include<cassert>
void DP::operator+=(DP &b){
    DP c;
    c.f[0].resize(min(k+1,(int)(f[0].size()+b.f[0].size())-1));
    c.f[1].resize(min(k+1,(int)(f[0].size()+b.f[0].size())-1));
    for(int i=0;i<(int)f[0].size();i++)for(int j=0;j<(int)b.f[0].size()&&i+j<(int)c.f[0].size();j++){
            /*if(j>=(int)b.f[0].size())fprintf(stderr,"a=%d b=%d c=%d\n",f[0].size(),b.f[0].size(),c.f[0].size());
              assert(j<(int)b.f[0].size());*/
        c.f[0][i+j]=(c.f[0][i+j]+(long long)f[0][i]*(b.f[0][j]+b.f[1][j]))%mod;
        c.f[1][i+j]=(c.f[1][i+j]+(long long)f[1][i]*b.f[0][j])%mod;
    }
    f[0].clear();
    f[1].clear();
    b.f[0].clear();
    b.f[1].clear();
    *this=c;
}

测试点5

$n=144$，$k=20$，暴搜肯定也没戏……（之后直接忽略暴搜）

手动观察一下输入数据可以发现一些规律，比如缺某条边的点是等距分布的，再写个东西瞎xx判一下就可以发现这其实是一个$12\times 12$的网格图缺了一些边，然后写一个状压DP就好了。

判断程序：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cassert>
using namespace std;
const int maxn=255;
bool a[maxn][maxn];
int n,m,k,p,ans=0,id[35][35];
int main(){
    freopen("subset5.in","r",stdin);
    //freopen("what.out","w",stdout);
    int r=12,c=12,n=0;
    for(int i=1;i<=r;i++)for(int j=1;j<=c;j++)id[i][j]=++n;
    scanf("%*d%d%d%d",&m,&k,&p);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y]=a[y][x]=true;
    }
    for(int i=1;i<=r;i++)for(int j=1;j<=c;j++){
            if(i){
                a[id[i][j]][id[i-1][j]]=false;
                a[id[i-1][j]][id[i][j]]=false;
            }
            if(j){
                a[id[i][j]][id[i][j-1]]=false;
                a[id[i][j-1]][id[i][j]]=false;
            }
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)assert(!a[i][j]);
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

状压DP：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
bool a[255][255],down[75][255],right[75][255],ok[25][5005];
int n=12,m=12,e,k,p,id[75][255],f[25][5005][25];
int main(){
    freopen("subset5.in","r",stdin);
    freopen("subset5.out","w",stdout);
    int cnt=0;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)id[i][j]=++cnt;
    scanf("%*d%d%d%d",&e,&k,&p);
    while(e--){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y]=a[y][x]=true;
    }
    for(int i=1;i<n;i++)for(int j=1;j<=m;j++)if(a[id[i][j]][id[i+1][j]])down[j][i-1]=true;
    for(int i=1;i<=n;i++)for(int j=1;j<m;j++)if(a[id[i][j]][id[i][j+1]])right[j][i-1]=true;
    for(int j=1;j<=m;j++){
        for(int s=0;s<(1<<n);s++){
            bool bad=false;
            for(int i=0;i<n-1;i++)if(down[j][i]&&((s>>i)&1)&&((s>>(i+1))&1)){
                bad=true;
                break;
            }
            ok[j][s]=!bad;
        }
    }
    ok[0][0]=true;
    f[0][0][0]=1;
    for(int j=0;j<m;j++)for(int s=0;s<(1<<n);s++)if(ok[j][s]){
                //for(int l=0;l<=k;l++)if(f[j][s][l])fprintf(stderr,"f[%d][%d][%d]=%d\n",j,s,l,f[j][s][l]);
        for(int t=0;t<(1<<n);t++)if(ok[j+1][t]){
            bool bad=false;
            for(int i=0;i<n;i++)if(right[j][i]&&(((s&t)>>i)&1)){
                bad=true;
                break;
            }
            if(bad)continue;
            int siz=__builtin_popcount(t);
            for(int l=0;l+siz<=k;l++)f[j+1][t][l+siz]=(f[j+1][t][l+siz]+f[j][s][l])%p;
        }
    }
    int ans=0;
    for(int s=0;s<(1<<n);s++)ans=(ans+f[m][s][k])%p;
    printf("%d",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

UPD：

我好像逗比了……这个网格图是满的，并不缺边……囧囧囧，我还是太菜了……

测试点7

点数和边数都比较大，不过发现$m-n$才有$4$，猜想这个图可以表示成任意一棵生成树+5条非树边。大力判一波之后可以发现图确实是连通的，那么$3^5$大力枚举每条边的状态之后再套一个$O(n^2)$的树形DP即可。

这次跑的时间比较长，为了不浪费时间，可以在跑暴力的时候来一发tetris（逃

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cassert>
using namespace std;
const int maxn=6005;
int findroot(int);
void mergeset(int,int);
void dfs(int);
void add(int,int);
vector<int>G[maxn];
bool vis[maxn];
int n,m,K,p,a[maxn],size[maxn],f[maxn][maxn][2],anc[maxn];
int main(){
    freopen("subset7.in","r",stdin);
    freopen("subset7.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&K,&p);
    for(int i=1;i<=n;i++)anc[i]=i;
    int u[55]={0},v[55]={0},cnt=0;
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        if(findroot(x)==findroot(y)){
            u[cnt]=x;
            v[cnt]=y;
            fprintf(stderr,"(%d,%d) cnt=%d\n",u[cnt],v[cnt],cnt);
            cnt++;
        }
        else{
            G[x].push_back(y);
            G[y].push_back(x);
            mergeset(x,y);
        }
    }
    memset(a,-1,sizeof(a));
    int ans=0;
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)for(int k=0;k<3;k++)for(int l=0;l<3;l++)for(int m=0;m<3;m++){
                        if((!u[0]&&i)||(!u[1]&&j)||(!u[2]&&k)||(!u[3]&&l)||(!u[4]&&m))continue;
        memset(a,-1,sizeof(a));
        fprintf(stderr,"i=%d j=%d k=%d l=%d m=%d\n",i,j,k,l,m);

        if(i==0){
            a[u[0]]=1;
            a[v[0]]=0;
        }
        else if(i==1){
            a[u[0]]=0;
            a[v[0]]=1;
        }
        else a[u[0]]=a[v[0]]=0;

        if(j==0){
            a[u[1]]=1;
            a[v[1]]=0;
        }
        else if(j==1){
            a[u[1]]=0;
            a[v[1]]=1;
        }
        else a[u[1]]=a[v[1]]=0;

        if(k==0){
            a[u[2]]=1;
            a[v[2]]=0;
        }
        else if(k==1){
            a[u[2]]=0;
            a[v[2]]=1;
        }
        else a[u[2]]=a[v[2]]=0;

        if(l==0){
            a[u[3]]=1;
            a[v[3]]=0;
        }
        else if(l==1){
            a[u[3]]=0;
            a[v[3]]=1;
        }
        else a[u[3]]=a[v[3]]=0;

        if(m==0){
            a[u[4]]=1;
            a[v[4]]=0;
        }
        else if(m==1){
            a[u[4]]=0;
            a[v[4]]=1;
        }
        else a[u[4]]=a[v[4]]=0;

        memset(vis,0,sizeof(vis));
        memset(f,0,sizeof(f));
        memset(size,0,sizeof(size));
        dfs(1);assert(size[1]==n);
        ans=(ans+(f[1][K][0]+f[1][K][1])%p)%p;
        fprintf(stderr,"ans+=%d\n",(f[1][K][0]+f[1][K][1])%p);
    }
    printf("%d",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
int findroot(int x){return x==anc[x]?x:(anc[x]=findroot(anc[x]));}
void mergeset(int x,int y){anc[findroot(x)]=findroot(y);}
void dfs(int x){
    //memset(f[x],0,sizeof(int)*(n+3));
    vis[x]=true;
    size[x]=1;
    if(a[x]==0)f[x][0][0]=1;
    else if(a[x]==1)f[x][1][1]=1;
    else f[x][0][0]=f[x][1][1]=1;
    for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]]){
            dfs(G[x][i]);
            add(x,G[x][i]);
        }
}
void add(int x,int y){
    static int g[maxn][2];
    memset(g,0,sizeof(g));
    for(int i=0;i<=size[x];i++)for(int j=0;j<=size[y];j++){
        g[i+j][0]=(g[i+j][0]+(long long)f[x][i][0]*((f[y][j][0]+f[y][j][1])%p)%p)%p;
        g[i+j][1]=(g[i+j][1]+(long long)f[x][i][1]*f[y][j][0]%p)%p;
    }
    //for(int i=0;i<=size[x];i++)printf("(%d,%d) ",f[x][i][0],f[x][i][1]);printf("\n");
    //for(int i=0;i<=size[y];i++)printf("(%d,%d) ",f[y][i][0],f[y][i][1]);printf("\n");
    memcpy(f[x],g,sizeof(g));
    size[x]+=size[y];
    //for(int i=0;i<=size[x];i++)printf("(%d,%d) ",f[x][i][0],f[x][i][1]);printf("\n\n");
}

话说在这个点上因为几个NC错误卡了至少一个小时，我是不是菜得没救了……

好吧……还是高估了我的水平，除了这6个点之外剩下的似乎并不会做……

（其实测试点8是可以%论文来做的，然而我懒得学了，毕竟感觉NOI不一定用得上，还是好好复习比较好……逃）

由于填坑人弱菜AntiLeaf在这个坑里摔出*了，此坑已弃