祝馀宫

题面题目链接大秦 为你打开 题目传送门 备用题面一个无向图中有n顶点和m条边，无重边无自环。顶点从1到n编号。 Q次询问，每次询问u,vu,v之间是否存在一条长度为奇数的简单路径。 注：简单路径为不经过重复的点的路径。 思路我们思考如何才能有一个长度为奇数的简单路径： 本来就有 有奇环。 为什么说是有奇环呢？不是说不能经过重复点吗？这里指的其实是经过的路径上有奇环，因为奇环可以分成两边走，由于是奇环，所以两边的奇偶性一定不一样，这样就给了我们选择路径奇偶性的余地。 那么本来就有是什么情况呢？如果两个点在一个 Dfs 生成树上面的深度奇偶性不同，那么他们就属于本来就有奇数路径。因为这样的话 $u\rightarrow root\rightarrow v$ 这样的路径一定是奇数的简单路径。那么如果奇偶性一样怎么办，那么我们就只能指望于两个点到他们 LCA 的路径上有奇环了。不难发现只要至少有一个奇环我们就是可以的。那么就只需要另外处理一个倍增数组，记录这里奇环的数量就可以了。 那么处理奇环也很简单，Tarjan 做点双连通分量，一个没有割点的图绝对有环，我们只需要判断是不是奇环，然后用 ...

题面大秦为你打开题目传送门 题目描述Siruseri 城中的道路都是单向的。不同的道路由路口连接。按照法律的规定，在每个路口都设立了一个 Siruseri 银行的 ATM 取款机。令人奇怪的是，Siruseri 的酒吧也都设在路口，虽然并不是每个路口都设有酒吧。 Banditji 计划实施 Siruseri 有史以来最惊天动地的 ATM 抢劫。他将从市中心出发，沿着单向道路行驶，抢劫所有他途径的 ATM 机，最终他将在一个酒吧庆祝他的胜利。 使用高超的黑客技术，他获知了每个 ATM 机中可以掠取的现金数额。他希望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可以经过同一路口或道路任意多次。但只要他抢劫过某个 ATM 机后，该 ATM 机里面就不会再有钱了。 例如，假设该城中有 $6$ 个路口，道路的连接情况如下图所示： 市中心在路口 $1$，由一个入口符号 → 来标识，那些有酒吧的路口用双圈来表示。每个 ATM 机中可取的钱数标在了路口的上方。在这个例子中，Banditji 能抢劫的现金总数为 $47$，实施的抢劫路线是：$1-2-4-1-2-3 ...

题面题目链接大秦 为你打开 题目传送门 备用题面一个有向图中有 $n$ 顶点和 $m$ 条边，顶点从 $1$ 到 $n$ 编号。 给定起点 $s$ ，问最少要添加多少条边，才能使得s到其它所有顶点都有可达路径。 思路我们就只需要看我不可达的点可以到达多少我不可达的点，然后选择到达我不可达的点多的点，把他们标记成我可达的点，一直贪心下去即可。 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124#pragma GCC optimize(2)#pragma GCC optimize(3, "Ofast&quo ...

题面题目链接大秦 为你打开 题目传送门 备用题面求割点。 思路那么这道题既然是求割点的模板题，我们就来浅浅回顾一下 Tarjan 求割点是怎么回事。 对于 Tarjan 最最基础的一些变量定义，不知道建议直接 出门右转看我 Tarjan 博文 那么言归正传，其实说割点就是 low 值大于 dfn 值，因为如果我最小的点就是到达我的子孙方向的，那么我就是必经之路，所以这个点就是割点。另外这个点如果是根要特判，如果这个根有大于等于 2 的儿子，那么它还是割点。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122#pragma ...

题面题目链接大秦 为你打开 题目传送门 备用题面给定一个 $N$ 个顶点，$M$ 条边的无向连通图，顶点从 $1$ 到 $N$ 编号。 问至少要添加几条边，才能使其变为双连通图。 思路这道题目不难想到缩点以后，找到度为 $1$ 的点（因为这样一切就断了）然后这样点的个数我们要把他们连到一起，答案就是这样点的数量除以二去上底。 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131#pragma GCC optimize(2)#pragma GCC optimize(3, &q ...

题面大秦为你打开题目传送门 题目描述给定一个 $N$ 个顶点 ，$M$ 条边的无向连通图，顶点从 $1$ 到 $N$ 编号。 再给出一个 $\tt dfs$ 生成树。 现在要求从 $\tt dfs$ 生成树中选最少的边集合 $S$ ，使得图中每一个简单环中最少有一条边属于 $S$ 。 题解这道题目就是记录每一个点可以到达的点的集合，如果可以到达父亲节点算作一个答案 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108#pragma GCC optimize(2)#pragma GCC optimize(3, "Ofast", "inline")#include< ...

题面题目链接大秦 为你打开 题目传送门 备用题面给一棵 $n$ 个节点的树, 节点编号为 $1$ ~ $n$ ，每条边有权值。 对于一棵树，最长的路径为树的直径，可能不唯一。 求该树的直径长度是多少，以及有多少条边满足所有的直径都经过该边。 思路首先直径肯定都会算，我们记录一个答案，把直径的一个端点作为根建树，然后对于每一个点记录一下该节点的子树中到根节点最远的是多远，顺便记录一下一共有几个，如果当前点是直径上的点的话我们先判断一下是否存在两个及以上最长路径，如果是的话答案缩小到深度减一，如果存在子树中到根节点的距离的最大值等于根节点到该点的距离，我们直接将答案减去深度减一直接输出即可。 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210 ...

题面题目链接大秦 为你打开 题目传送门 题目翻译给一棵 $n$ 个节点的树，节点编号为 $1$ ~ $n$ ，每条边权值都为 $1$ 。 另给定一个整数 $k$ ，求距离刚好为 $k$ 的点对有多少。 注：$(u,v)$ 和 $(v,u)$ 算同一个点对。 思路我们设 $dp[i][k]$ 表示距离 $i$ 号点距离为 $k$ 的点的数量。那么显然的可以得到转移方程： dp[root][j] = \sum dp[son][j-1]但是这时候只有我的子树方向的点，所以还要算上不是我的子树方向的点，那就是： dp[root][j]=dp[root][j]+dp[son][j - 1] - dp[root][j-2]然后这样就是统计和然后除以 $2$ ，就可以了 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586 ...

题面大秦为你打开题目传送门 题目描述小 C 最近学了很多最小生成树的算法，Prim 算法、Kruskal 算法、消圈算法等等。正当小 C 洋洋得意之时，小 P 又来泼小 C 冷水了。小 P 说，让小 C 求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是 $E_M$，严格次小生成树选择的边集是 $E_S$，那么需要满足：($value(e)$ 表示边 $e$ 的权值) $\sum_{e \in E_M}value(e)<\sum_{e \in E_S}value(e)$。 这下小 C 蒙了，他找到了你，希望你帮他解决这个问题。 输入格式第一行包含两个整数 $N$ 和 $M$，表示无向图的点数与边数。 接下来 $M$ 行，每行 $3$ 个数 $x,y,z$ 表示，点 $x$ 和点 $y$ 之间有一条边，边的权值为 $z$。 输出格式包含一行，仅一个数，表示严格次小生成树的边权和。 样例 #1样例输入 #112345675 61 2 1 1 3 2 2 4 3 3 5 4 3 4 3 4 5 6 样例输出 #1111 提示数据中无向 ...