期待已久的ZJOI day1终究落幕，有人欢笑有人忧愁。

虽然还是有许多需要总结反思的地方，但结果还算满意。付出总会有回报。不会错的

第一天

到宾馆，闷声打隔膜，看电视。

第二天

上午听绍一神犇讲课，预习了一下神犇的课件，最后看上去有好几题没讲的样子。

下午听jcvb神讲课，果然神犇讲的题目还是很有难度的像我这种逗比选手想不出来。

然后听数国讲了一题，说是数据范围10W？结果想了一天没想出来。感觉智商余额不足。

晚上闷声打隔膜，战绩：败2胜0

第三天

上午听杜教讲自动机，听了一会后感觉用处不是特别大就开始土云云。

中午打隔膜，战绩：败2胜0

下午听约大爷讲怎么写编译器？感觉太神，然后又因为有点中暑闷声睡大觉

然后xllend3、fsygd、cenbo讲课，然后才知道原来上面数国讲的那题数据范围是500。果然是愚人节？

晚上上机打了个ntt模板，然后define滚粗了，调了10分钟发现算3^2=667082563。

回宾馆后打了会单机小隔膜。闷声睡大觉

第四天

看上去起得有晚，饭吔得有点匆忙

考试开始后，开始没有草稿纸，先看题。

T1看上去像是什么数据结构乱搞

T2看上去像是xgt专用的智商题

T3看上去好大！感觉完全不可做，hash不行，自动机看上去也不行

然后拿了草稿纸想T1，想完写了个树剖，加上调的时间共用2.5h

上了个厕所开始seT2

10分钟写了个50分暴力

然后感觉100分写不出来看T3

然后看到（最多只有20个子节点）感觉有屁用？

然后想，后缀自动机？感觉不能写？

然后滚粗再看T2

然后过了半小时想到子集dp

脑补了一下正确性感觉靠谱

码了30分钟开始调

然后大样例一直过不掉

然后最后都没过掉

出考场时我总感觉自己150要滚粗的样子

然后听说很多人都A掉了T3？

感觉他们都好神

然后听说T3是后缀自动机？

然后感觉我完全没听懂他们的做法？

为什么20个子节点就可以建400W的自动机？

这有关系么？

然后发现题目看错，滚粗

居然是20个叶子节点。

果然逗比选手每天犯这种错误

然后听说大家考得都不是很好的样子？

（后记：回到学校后晚自修第三节课没事干又推了一下T2的dp方程，发现我犯了一个超傻逼的错误（当然还能写）然后就不高兴地立起了flag：考试延长3小时我就能AK）

下面放我的题解

T1：首先把1作为树根

a[i]表示i点有多少军队

f[i]表示以i为根的子树中有多少军队

len[i]表示点i与根节点的距离

g[i]表示sigma len[j]*a[j] j在以i为根的子树中

考虑，我们要找一个点，他的f[i]>=(f[1]+1)/2并且他的所有儿子都不满足这个性质

正确性易证

然后考虑每次修改找这个点

考虑所有满足f[i]>=(f[1]+1)/2的点都在一条链上，并且

然后要找深度最大的这个点

然后就可以在链上二分找，这个可以用树剖完成

然后计算答案。比如你已经找到这个点x

然后ans=sigma(g[i]-g[son[i]]+(len[x]-2*len[i])*(f[i]-f[son[i]])

son[i]表示满足那个f[son[i]]>=(f[1]+1)/2的i的儿子，如果没有就为0

然后考虑展开ans=g[1]+f[1]*len[x]-2*sigma f[i]*(len[dad[i]]-len[i])

前两项不说了，最后一项可以考虑用树剖维护。

然后就没了

T2

首先，对所有边排序，然后对于每条边，我们都选，然后只要选到整张图联通为止

然后就可以考虑dp f[i][j]表示i这个子集，用j条边后联通的方案数（第j条边使他联通）

g[i][j]表示i这个子集，用了j条边，并且联通的方案数（就是联通后可以继续加边）

然后考虑转移。枚举i的子集k，补集t然后f[i][j]=sigma g[k][l]*g[t][j-l-1]*C(l,j-1)

然后g[i][j]=g[i][j-1]*(i子集内部边的总数-j+1)+f[i][j]

总的时间复杂度为3^n(枚举子集，以及子集的子集)*m^2（卷积）但是由于子集的边数少，所以靠谱

T3

后缀自动机

只要你会后缀自动机你就会做这题！

总而言之，陈老师的题目还算良心，没有毒瘤题目，只是可能高二的学长们因为压力太大不敢写标算导致普遍分数不高。

希望所有考挂了的同学再接再厉，更上一层楼，best wishes to you~

顺带膜一下180的qwer和同样150的zhl= =