众所周知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在这个坑里摔出*了，此坑已弃

前两天学了学高斯消元版的一般图最大匹配，抄了抄各位dalao们的代码

今天重新看自己写的代码，发现有一个地方抄错了

//In function Gauss(int A[][maxn],int B[][maxn],n)
if(B){
    swap(id[i],id[j]);
    for(int k=1;k<=n;k++)swap(B[i][k],B[j][k]);
}

而代码里对Gauss这个函数的两次调用分别是这样的

Gauss(A,NULL,n);
......
Gauss(A,B,n);

第一次高斯消元是为了找出所有在最大匹配中的点，但由于高斯消元的过程中可能会进行行的交换，因此需要维护一个id数组表示每个点对应的行号

(讲真其实还是没明白为啥这个东西是每个点对应的行号，不应该是每行对应的点的编号么……然而这样又解释不清代码在写什么了，囧囧囧……)

然而正常的写法应该是在第一次高斯消元时维护id[]，第二次高斯消元时维护与否都无所谓了，显然我这个是搞反了

但是还是可以过掉所有的数据和hack数据，手动构造了几组也卡不掉，感觉很神奇

这个代码应该是错的了，数据的构造思路应该是找一个点$x$($x>1$)使得$x$和$1$之间有连边但$x$不可能在最大匹配中，但是想了想并没有找到满足这种情况的数据

因此写了这篇博客，虚心请求诸位dalao提供一组hack数据，以解心中疑问，如有dalao愿意相助，不胜感激……

两三个月之前写了紫荆花之恋，bzoj上跑过去了，交到uoj上死活MLE

昨天闲的没事又卡了卡内存，然而还是MLE了

感觉很不开心，于是刚才造了一波极限数据去hack

然后就hack了一波 @yyhslyz 的代码，结果不小心hack成功了= =

http://uoj.ac/hack/3192

让我静静……

UPD：

重评完辣，世界又恢复和平辣

大概看了看，好像这波hack卡掉了将近二十份代码，其中有不少MLE的

感觉心理平衡多了233333

UPD：

下午重写了一遍，终于过了

http://uoj.ac/submission/138458

感觉心情舒畅了许多呢~

(不要问我后来的几次hack是怎么回事

是不是vfk觉得出题人太**于是就把这题给ban了……

没错，就是那道SPOJ2666 QTREE4......

那道题我写了一个多小时......调了一晚上......然而还是没调出来......

COGS上最后一组数据不过，扒下来之后对着数据调了半天也没什么进展，调不下去了......

发现把以1为根建树换成以n为根建树就行......并且随便换一个都可以(问题是就是1不行

所以......这是为啥......我实在调不出来了，跪求会动态树分治的dalao纠错......

我写的是动态边分治......

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn=400010;
struct edge{int to,w,prev;bool vis;edge():to(0),w(0),prev(0),vis(false){}}e[maxn<<1];//存新树的边，vis代表是否已被删除
struct A{//大根堆，维护答案
    int x,d;
    A(int x,int d):x(x),d(d){}
    bool operator<(const A &a)const{return d<a.d;}
};
void dfs_prework(int);//预处理，添虚点
void addedge(int,int,int);//在新树上添一条边
void build(int,int,int);//对以x为根的子树建边分治树
void dfs_getedge(int,int,int&);//找中心边
void dfs_getdis(int,int,int,int);//求距离
void modify(int);//翻转颜色
int getans(int);//更新点x对应的堆并返回当前答案
vector<int>G[maxn],W[maxn];//原树的边
int last[maxn],len=0,size[maxn]={0},p[maxn]={0};//建边分治树用的辅助数组
int eid[maxn],d[maxn][25],id[maxn][25],dir[maxn][25];//在深度为k的边分治树中的距离和左右，对应的点的编号
priority_queue<A>heap,q[maxn][2];//全局堆和边分治树的每个点的堆
int n,m,cnt,x,y,z,col[maxn]={0},white;//记一下每个点现在的颜色，0白1黑
char c;
int main(){
    freopen("QTREE4.in","r",stdin);
    freopen("QTREE4.out","w",stdout);
    memset(last,-1,sizeof(last));
    memset(eid,-1,sizeof(eid));
    scanf("%d",&n);
    cnt=white=n;
    for(int i=1;i<n;i++){
        scanf("%d%d%d",&x,&y,&z);
        G[x].push_back(y);
        W[x].push_back(z);
        G[y].push_back(x);
        W[y].push_back(z);
    }
    dfs_prework(1);//getchar();getchar();
    memset(p,0,sizeof(p));//printf("cnt=%d\n",cnt);
    cnt=0;
    build(1,0,n);//printf("\n");
    scanf("%d",&m);
    while(m--){
        scanf(" %c",&c);
        if(c=='C'){
            scanf("%d",&x);
            modify(x);
        }
        else{
            while(!heap.empty()&&getans(heap.top().x)!=heap.top().d){
                //printf("heap.pop()=(%d,%d)\n",heap.top().x,heap.top().d);
                x=heap.top().x;
                heap.pop();
                if((z=getans(x))!=1<<31)heap.push(A(x,z));
            }
            //printf("heap.size()=%d\n",heap.size());
            if(!white)printf("They have disappeared.\n");
            else if(white==1)printf("0\n");
            else printf("%d\n",max(heap.top().d,0));
        }
    }
    return 0;
}
void dfs_prework(int x){//预处理，添虚点
    for(int i=0;i<(int)G[x].size();i++)if(G[x][i]!=p[x]){
        p[G[x][i]]=x;
        dfs_prework(G[x][i]);
    }
    A y(0,0),z(0,0);
    queue<A>q;
    for(int i=0;i<(int)G[x].size();i++)if(G[x][i]!=p[x])q.push(A(G[x][i],W[x][i]));
    while((int)q.size()>2){
        y=q.front();q.pop();
        z=q.front();q.pop();
        cnt++;
        addedge(cnt,y.x,y.d);
        addedge(y.x,cnt,y.d);
        addedge(cnt,z.x,z.d);
        addedge(z.x,cnt,z.d);
        q.push(A(cnt,0));
    }
    while(!q.empty()){
        y=q.front();q.pop();
        addedge(x,y.x,y.d);
        addedge(y.x,x,y.d);
    }
}
void addedge(int x,int y,int z){//在新树上添一条边
    e[len].to=y;//printf("addedge(%d,%d,%d)\n",x,y,z);
    e[len].w=z;
    e[len].prev=last[x];
    last[x]=len++;
}
void build(int x,int k,int s){//对以x为根的子树建边分治树
    if(s<=1)return;
    int rt=++cnt;//printf("\n");printf("build(%d,%d,%d)\n",x,k,s);
    dfs_getedge(x,s,eid[rt]);
    int u=e[eid[rt]^1].to,v=e[eid[rt]].to;//printf("id=%d u=%d v=%d w=%d\n",eid[rt],u,v,e[eid[rt]].w);
    e[eid[rt]].vis=e[eid[rt]^1].vis=true;
    p[u]=p[v]=d[u][k]=d[v][k]=0;
    dfs_getdis(u,rt,k,0);
    dfs_getdis(v,rt,k,1);
    if(!q[rt][0].empty()&&!q[rt][1].empty()){
        //printf("top=(%d,%d) w=%d\n",q[rt][0].top().d,q[rt][1].top().d,e[eid[rt]].w);
        //printf("heap.push(%d,%d)\n",rt,q[rt][0].top().d+q[rt][1].top().d+e[eid[rt]].w);
        //if(q[rt][0].top().d+q[rt][1].top().d+e[eid[rt]].w>=10000)printf("%d\n",q[rt][0].top().d+q[rt][1].top().d+e[eid[rt]].w);
        heap.push(A(rt,q[rt][0].top().d+q[rt][1].top().d+e[eid[rt]].w));
    }
    //else printf("EMPTY\n");
    build(u,k+1,s-size[v]);
    build(v,k+1,size[v]);
}
void dfs_getedge(int x,int s,int &id){//找中心边
    size[x]=1;//printf("dfs_getedge(%d,%d)\n",x,s);
    for(int i=last[x];i!=-1;i=e[i].prev)if(!e[i].vis&&e[i].to!=p[x]){//printf("i=%d\n",i);
        p[e[i].to]=x;
        dfs_getedge(e[i].to,s,id);
        size[x]+=size[e[i].to];
        if(id==-1||max(size[e[i].to],s-size[e[i].to])<max(size[e[id].to],s-size[e[id].to]))id=i;
    }
}
void dfs_getdis(int x,int rt,int k,int c){//求距离，顺便完成对对应层id和dir的标号
    //printf("dfs_getdis(%d,%d,%d,%d)\n",x,rt,k,c);
    if(x<=n){
        //printf("q[%d][%d].push(%d,%d)\n",rt,c,x,d[x][k]);
        q[rt][c].push(A(x,d[x][k]));
    }
    id[x][k]=rt;dir[x][k]=c;
    for(int i=last[x];i!=-1;i=e[i].prev)if(!e[i].vis&&e[i].to!=p[x]){//printf("i=%d\n",i);
        p[e[i].to]=x;
        d[e[i].to][k]=d[x][k]+e[i].w;
        dfs_getdis(e[i].to,rt,k,c);
    }
}
void modify(int x){//翻转颜色
    if(col[x])white++;
    else white--;
    col[x]^=1;
    for(int i=23;i>=0;i--)if(id[x][i]){//如果是0表示深度过大不存在
        getans(id[x][i]);
        if(!col[x]){//原为黑色，入堆
            if((q[id[x][i]][dir[x][i]].empty()||q[id[x][i]][dir[x][i]].top().d<d[x][i])&&!q[id[x][i]][dir[x][i]^1].empty()){
                heap.push(A(id[x][i],d[x][i]+q[id[x][i]][dir[x][i]^1].top().d+e[eid[id[x][i]]].w));
                //printf("heap.push(%d,%d)\n",id[x][i],d[x][i]+q[id[x][i]][dir[x][i]^1].top().d+e[eid[id[x][i]]].w);
            }
            //printf("q[%d][%d].push(%d,%d)\n",id[x][i],dir[x][i],x,d[x][i]);
            q[id[x][i]][dir[x][i]].push(A(x,d[x][i]));
        }
        //否则原为白色，应当出堆，但我们只需等待这个堆被询问时再更新即可(懒惰更新)
    }
}
int getans(int x){//更新点x对应的堆并返回当前答案
    //printf("getans(%d)\n",x);
    while(!q[x][0].empty()&&col[q[x][0].top().x])q[x][0].pop();//更新左边的堆
    while(!q[x][1].empty()&&col[q[x][1].top().x])q[x][1].pop();//更新右边的堆
    if(q[x][0].empty()||q[x][1].empty())return 1<<31;//如果左右有一个为空则说明有一半没有白点
    else return q[x][0].top().d+q[x][1].top().d+e[eid[x]].w;
}
/*
5
1 2 1
2 3 1
2 4 -1
4 5 3
100000
A
C 5
A
C 3
A
C 5
A
C 5
A
C 5
A
C 5
A
C 2
A
C 1
A
C 4
A
C 2
A
C 4
A
C 3
A
C 2
A
*/
/*
SPOJ2666 QTREE4
基本思路就是边分治，每层中心边的两个端点存一个堆维护所代表子树中所有白点的距离，
再存一个全局堆维护边分治树的每个点所产生的答案。
翻转时在边分治树上修改logn个节点的堆即可，查询直接取全局堆的最大值，O(1)。
细节问题：
1.对每个点存它在深度为k的点分治树中到中心边的距离和属于中心边的哪一边，方便修改。
2.开一个数组记录每个点当前颜色，取最大值时方便查询最大值是否合法，不合法则pop掉重新取。
*/

最后那组数据太大了，我就不往上放了......

UPD： 估计是COGS数据太弱了......我到vjudge上交结果怎么换根都WA......

UPD： 改成点分治就过了......然而vjudge上TLE了......囧囧囧

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn=100010;
struct binary_heap{
    priority_queue<int>q1,q2;
    void push(int x){q1.push(x);}
    int top(){
        while(!q2.empty()&&q1.top()==q2.top()){
            q1.pop();
            q2.pop();
        }
        return q1.top();
    }
    int top2(){
        int fir=top();
        pop();
        int sec=top();
        push(fir);
        return sec;
    }
    void pop(){
        while(!q2.empty()&&q1.top()==q2.top()){
            q1.pop();
            q2.pop();
        }
        q1.pop();
    }
    void erase(int x){q2.push(x);}
    int size(){return (int)q1.size()-(int)q2.size();}
    bool empty(){return !size();}
}heap,q[maxn],q1[maxn][20];
void build(int,int,int,int);
void dfs_getcenter(int,int,int&);
void dfs_getdis(int,int,int);
void modify(int);
vector<int>G[maxn],W[maxn];
int size[maxn]={0},son[maxn]={0};
int depth[maxn]={0},p[maxn]={0},d[maxn][20],id[maxn][20];
bool vis[maxn]={false},col[maxn]={false};
int n,m,white,x,y,z;
char c;
int main(){
    freopen("QTREE4.in","r",stdin);
    freopen("QTREE4.out","w",stdout);
    scanf("%d",&n);
    white=n;
    for(int i=1;i<n;i++){
        scanf("%d%d%d",&x,&y,&z);
        G[x].push_back(y);
        W[x].push_back(z);
        G[y].push_back(x);
        W[y].push_back(z);
    }
    heap.push(0);
    build(1,0,n,0);
    scanf("%d",&m);
    while(m--){
        scanf(" %c",&c);
        if(c=='C'){
            scanf("%d",&x);
            modify(x);
        }
        else{
            if(!white)printf("They have disappeared.\n");
            else if(white==1)printf("0\n");
            else printf("%d\n",heap.top());
        }
    }
    return 0;
}
void build(int x,int k,int s,int pr){
    int u=0;
    dfs_getcenter(x,s,u);
    vis[x=u]=true;
    p[x]=pr;
    depth[x]=k;
    q[x].push(0);
    if(s<=1)return;
    for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]]){
        d[G[x][i]][k]=W[x][i];
        p[G[x][i]]=0;
        dfs_getdis(G[x][i],G[x][i],k);
        q[x].push(q1[G[x][i]][k].top());
    }
    heap.push(q[x].top()+q[x].top2());
    for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]])build(G[x][i],k+1,size[G[x][i]],x);
}
void dfs_getcenter(int x,int s,int &u){
    size[x]=1;
    son[x]=0;
    for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]]&&G[x][i]!=p[x]){
        p[G[x][i]]=x;
        dfs_getcenter(G[x][i],s,u);
        size[x]+=size[G[x][i]];
        if(size[G[x][i]]>size[son[x]])son[x]=G[x][i];
    }
    if(!u||max(s-size[x],size[son[x]])<max(s-size[u],size[son[u]]))u=x;
}
void dfs_getdis(int x,int v,int k){
    q1[v][k].push(d[x][k]);
    size[x]=1;id[x][k]=v;
    for(int i=0;i<(int)G[x].size();i++)if(!vis[G[x][i]]&&G[x][i]!=p[x]){
        p[G[x][i]]=x;
        d[G[x][i]][k]=d[x][k]+W[x][i];
        dfs_getdis(G[x][i],v,k);
        size[x]+=size[G[x][i]];
    }
}
void modify(int x){
    col[x]^=true;
    if(col[x]){
        if(q[x].size()>1)heap.erase(q[x].top()+q[x].top2());
        q[x].erase(0);
        if(q[x].size()>1)heap.push(q[x].top()+q[x].top2());
        white--;
    }
    else{
        if(q[x].size()>1)heap.erase(q[x].top()+q[x].top2());
        q[x].push(0);
        if(q[x].size()>1)heap.push(q[x].top()+q[x].top2());
        white++;
    }
    for(int u=p[x],k=depth[x]-1;u;u=p[u],k--){
        if(col[x]){
            if(q[u].size()>1)heap.erase(q[u].top()+q[u].top2());
            q[u].erase(q1[id[x][k]][k].top());
            q1[id[x][k]][k].erase(d[x][k]);
            if(!q1[id[x][k]][k].empty())q[u].push(q1[id[x][k]][k].top());
            if(q[u].size()>1)heap.push(q[u].top()+q[u].top2());
        }
        else{
            if(q[u].size()>1)heap.erase(q[u].top()+q[u].top2());
            if(!q1[id[x][k]][k].empty())q[u].erase(q1[id[x][k]][k].top());
            q1[id[x][k]][k].push(d[x][k]);
            q[u].push(q1[id[x][k]][k].top());
            if(q[u].size()>1)heap.push(q[u].top()+q[u].top2());
        }
    }
}
/*
SPOJ2666 QTREE4
动态树分治，这次改用点分治。
每个重心的子树存一个堆维护到重心最远的白点，每个重心也存一个堆维护子树的答案，
重心的堆的前两大的元素就可以用来更新答案，把答案扔到一个全局堆里。
翻转时跳点分治树并修改对应子树和重心的堆，修改时顺便更新一下全局堆，
查询时O(1)取全局堆最大值即可。
*/