FWT的本质与 $k$ 进制FWT/高维DFT的探究

我以前在学啥啊。。。

「WC2019」数树

我好菜啊。为什么你们都是数数大师。

NOIP2020 sol

比csp出的好些。

九省联考2018乱写

省选联考题比ZJOI阳间得多。。。

鸣谢red的“遗产”

LOJ 2269. 「SDOI2017」切树游戏

给一棵$n$个点的树，点有点权且小于$m$。定义一个连通块的权值为点权异或和。

$Q$次操作，单点修改点权或询问满足权值为$x$的非空连通块数量，模$10007$

$n,Q\le 3\times 10^4,m\le 128$

「九省联考 2018」秘密袭击

给一棵树，点有点权$w_i$。给定$k$,求所有大小至少为$k$的连通块的第$k$大点权和。模64123

$n\le 1666,w_i\le 1666.$ 时限5s.

一道有意思又有点套路的数数好题。（可惜被暴力草了？

「NOI2014」购票

给一棵以1为根的树，每个点$u$有属性$p_u,q_u,l_u$,边有边权。若$v$为$u$的祖先且$u,v$距离不超过$l_u$,则$u$可以花费$d(u,v)p_u+q_u$的代价跳到$v$上。问每个点跳到根的最短距离。

$n\le 2\times 10^5,p_u\le 10^6,q_u\le 10^{12},s_u\le l_u\le 2\times 10^{11},\sum s_u\le 10^{11}$

loj 2048. 「HNOI2016」最小公倍数

给一个$n$个点$m$条边的无向图，每条边有属性$a_i,b_i$.有$Q$次询问，每次询问给出$u,v,A,B$，你需要回答从点$u$到点$v$是否存在一条路径$P$（不要求是简单路径）满足 $\max_{e\in P}\{a_e\}=A$且$\max_{e\in P}\{b_e\}=B$

$n,q\le 5\times 10^4,m\le 10^5.$

My solution:

考虑如果我们得到了图$G(A,B)=(V,\{e|a_e\le A,b_e\le B\})$，如何处理询问。维护一个并查集，将$G(A,B)$中所有边加入并维护连通块的$a_e$最大值和$b_e$最大值。

【判定】： $u,v$存在合法路径 $\Leftrightarrow $ $u,v$在$G(A,B)$中连通，且所在连通块$a_e$最大值为$A$,$b_e$最大值为$B$.

所以就是如何得到图$G(A,B)$了。大概就是要实现”不强制在线的二维可持久化并查集”。

yLOI2020 题解

扶咕咕6题4.5h残忍虐杀脑子慢手速慢选手Orz.不过题的质量是很好的，尤其是D题，我可能一辈子都出不出这种题，真的只能Orz。

「ZJOI2016」小星星

给一棵树 $ T $ 和一个图 $ G $ ,求将 $ T $ 上的点重标号后为 $ G $ 的子图的方案数。

$ n\le 17 $ .