[集训队互测2023]树哈希题解报告/bx/bx/bxzky！！！题意给定常数\(q\)，定义一棵以\(1\)为根的有根树\(T\)的\(s(T)\)为\(T\)中本质不同的子树数量，定义其权值为\(q^{s(T)}\)。给定\(n\)，对于\(i=1,\dots,n\)求所有大小为\(i\)的有标号有根树的权值之和对\(P\)

比较符合CCF造数据水平的题。思路首先可以用两个vector<pair<int,int>>v[N]分别将每一行、每一列的元素的权值与编号存储下来。那么可以对所有的\(v_i\)按照权值从小到大排序。那么发现对于所有的满足v[i][p].fst<v[i][q].fst的\((p,q)\)都可以建一条从\(p\)指

连通块计数的一种常见思路是钦定代表元，但发现这题的连边方式并不好指定一个代表元，那么只能尝试优化建图。我们尝试观察一下连边的情况，通过手玩样例获得一些几何直观的感受：345534453这个样例也许比较小，不过你真的把边画出来就会发现：连边形如\(2n-1\)条完整的斜线，中间

无聊的水题。无聊的水题IDLS喜欢上树。但是他并不想把一道数据结构题出到树上，他喜欢计Tree。这一天，他想自己造一棵树，他手头有\(N\)个树的节点，标号为\(1\simN\)，他会在它们之间连边，我们定义两颗树不同，当且仅当一对节点在一棵树中有连边，另一棵树中没有连边。但他不喜欢

开始补\(3\)月的做题。102.P7417由于\(f_G(a,b)\)可以走重边，所以我们只关心奇最短路以及偶最短路。判掉一下每个点只有奇数路径或偶数路径，即二分图，可以直接最短路树，在两题都需要特判掉。本题的重点在于确认\(G'\)的结构。考虑\((x_i,y_i)\)为不同奇偶的最短路数对，要

2024.6做题记录[JSOI2009]球队收益/球队预算考虑到要求最小总支出，想到最小费用流。首先容易发现，每场比赛都只有两种可能，即甲输乙赢或甲赢乙输。但是这样我们在跑费用流的时候显然需要考虑对于两个因素同时的影响，显然这样不好做。我们不妨假设剩下的比赛所有人都输，那么我们

涉及知识点：博弈论题意在一个树上，A和B可以通过边在节点间移动，每回合可以不移动，或者移动到有边直接连接的节点。A在抓B，当A与B处于同一个节点时即为被抓住，可以发现无论如何B最后都会被抓住，你需要添加最小数量的边使得B有策略可以永远不会被抓住。思路最终的必败态是

P6239[JXOI2012]奇怪的道路状压dp题目的限制可以把图拍成一个序列，在序列上考虑连边。求方案数，考虑dp。观察到\(k\)的大小、每个位置只有奇偶性和边数限制，可以设\(f_{i,j,s}\)表示考虑完前\(i\)个点，连了\(j\)条边，\([1,i]\)的度数状态为二进制\(s\)，此时\([1,i-k]\)

我们先不要管两个数按位与为\(1\)和两个数按位或为\(0\)的情况那么剩下的情况就是很简单的2-SAT问题就像并查集处理二元关系一样，这里最后建成的图一定是完全对称的，如下其中每个点都是一个SCC然后我们再来看剩下的两种情况，拿两个数按位与为\(1\)为例这就说明两个数必须要都是

A.DistanceMod5考虑一个点\(x\)向外的最短路树，如果两个点不满足\(dis_{i,x}=(dis_{j,x}+1)\bmod5\)或\(dis_{j,x}=(dis_{i,x}+1)\bmod5\)，那么这两个点一定没有连边，否则可能有连边。去除掉所有不可能的连边，剩下的连上边，发现这样是最优的。然后floydcheck

[AGC001F]WideSwaptrick+拓扑排序+线段树好题看到题目的操作，显然是复杂、不好的。为什么？交换操作是无序的，我们不知道交换后对各个部分的影响，难以分析。这时候我们注意到\(|P_i-P_j|=1\)的性质非常特殊，考虑从这里入手。如果以值域为系，那么会发现排列中的每个下标的交换在值

网络流的建图灵活，需要大量练习。一些常见套路：拆点：一般来说可以把一个点拆为一个入点和一个出点并连边，用于点边转化。连INF边：这种边不可能包含在最小割中，可以用来将点定向。建立超级源点和超级汇点：用于构建网络流模型。加辅助点：比较灵活，可以用于处理多种问题。做

byTheBigYellowDuck记录一些网络流建模的实际例题吧。相关链接：[[网络流24题]]，[[Day6PartI]]PartI.二分图&最大流满流：可以根据是否满流判断合法。匹配：一些二分图的经典建模还是要记住的，往往用一条\(S\toT\)的路径表示一次匹配。最小点覆盖=最大匹配=最大

2-SAT学习笔记P4782【模板】2-SAT2-SAT问题模型：构造bool变量\(x_1,x_2...x_n\)，使得满足一些限制一对\(x_1\)和\(x_2\)取值的条件合法。很显然根据Floyd传递闭包可以做到\(O(n^3+m)\)，但不太行。有\(O(n+m)\)的做法，发现对于每个条件是要我们选择一种取值（选择就很

4.6模拟赛T1困难的图论题意：找出所有在且仅在1个简单环中的边，输出编号的异或和。一个错误的想法：找边双连通分量，看边数是否等于点数反例：正解是点双所以我在想，为什么是点双，不是边双呢？什么时候找点双，什么时候找边双呢？T2中等的字符串已知\(m\)个关键词\(s_i\)，每出现

前言考虑单源最短路的一个性质：在有向图中，若存在边\(u\tov\)，边权为\(w\)，则\(\mathit{dis}_u+w\ge\mathit{dis}_v\)。正确性是显然的，因为如果反之\(\mathit{dis}_u+w<\mathit{dis}_v\)，我们就可以令\(\mathit{dis}_v\gets\mathit{dis}_u+w\)，原先的就不是最短路了，与题设矛盾

\(\text{分析}\)\(i\toa_i\)构成内向基环树，配合暴力程序观察内向基环树常见的一些特殊情况：灰色笔对应的是\(i\toa_i\)，黑色笔对应的是\(i\top_i\)，我们相当于要构造一个黑色的排列（若干环）使得每一条灰色边的起点可以通过一条或两条黑色边到达终点。\(a_i=i\)（全是自环）：可以任

非常有意思的一道题题意是给定一张图和它的bfs树，求一种可能的边的输入顺序。首先想这张图的bfs树为什么是这个，考虑那些非树边，如果这些边连接的两个点深度之差大于1，那么那个上面的点必定会先访问下面那个点，与题目矛盾。所以如果边连接的两个点深度相同，那么两个点必定在相同时间被

主要是讲一下tarjan算法的正确性我们的连边方案是对每一对已经有了的婚姻，从女方向男方连边，然后对于交往过的关系，从男方向女方连边分析题意不难发现，如果某一对夫妻处于一个环中，那么这对婚姻关系就是不稳定的其实从环这里已经可以看出来是SCC了，我们来简单说明一下首先，如果一对夫

DescriptionWarning：本文只介绍传递闭包在OI中的简单应用。传递闭包在OI中，一般用来处理图上点之间的连通性问题。它在图上体现在原图上任意两个直接或者间接可达的点都连边。在上图中，显然\(\{1,2\}\{2,3\}\{1,3\}\)均可达。在“传递闭包图”上如上三对点对都需要连边。

AGC010ERearranginglink题意：一个序列\(a_{1...n}\)，两个人游戏。先手打乱这个序列，然后后手可以多次选择一对相邻的互质的数交换。先手希望最终序列字典序尽量小，后手则相反。两人都绝顶聪明，求最终序列。\(1\len\le2000,\space1\lea_i\le10^8\)考虑不互质的两个数\(a_i,a

先看这篇题解这篇题解最开始的贪心我在赛时的时候想到了的，所以说博弈论完全是可以用贪心的，不要怕但是这里贪心还有一个问题，在对手攻击力比这张牌防御力大的区间中，对手可能有多张牌的防御力最大，这个时候难道每一个点都要连边吗？其实不用，连接其中随便一个就好了，因为我们发现，在每一

首先，若\(n\bmod3\neq0\)，则一定无解。考虑\(n\bmod3=0\)的情形：首先肯定是先进行一遍树形dp，求出树上每个节点\(x\)的子树大小\(size_x\)。若当前节点的\(size\)值\(=3\)，则说明需要切断当前节点于其父节点的连边，使得其子树成为一个大小为\(3\)的单独连通块。

A是谁瞪了半个小时不会*2000呀，是谁呀是谁呀。感觉这题比部分紫题都难。。。首先发现选取字符的顺序并不重要，所以\(t\)可以看成\(26\)个字符要选的个数。设字符\(c\)出现了\(x\)次，那么直接向汇点连流量为\(x\)费用为\(0\)的边。然后考虑\(s_i\)与每个字符的关

图论学习总结2拓补排序当给定的一张图是一张DAG（有向无环图）时，可以对该图进行拓补排序，在\(O(n+m)\)的时间内转移一些信息。通常用队列进行实现。拓补排序经常与其他算法进行结合，如DP。例题[POI2015]PUS(Pustynia)当一些数之间只给定了大小关系，要求一组可行解时，可以考虑