祝馀宫

题面题目链接大秦 为你打开 题目传送门 备用题面一个有向图中有 $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 提示数据中无向 ...

题面题目链接大秦 为你打开 题目传送门 题目翻译有一棵树，初始有4个结点： $1,2,3,4$ 。其中 $2,3,4$ 的父亲都是 $1$ 。 有 $q$ 个操作，每个操作给出指定的一个叶子结点 $v_i$ ，设当前操作执行前树中有 $n$ 个结点，然后添加结点 $n+1$，$n+2$ 号为 $v_i$ 儿子，添加完成之后树变成了 $n+2$ 个结点。 现在要求计算每次操作之后树的直径是多少。 思路因为每次增加两个同一个叶子节点的儿子，每次直径最多延长 $1$ ，直接对比选择那个节点后可以得到的最长直径即可（这题尼玛比卡常，得 O2 + O3 + fastIO 才可以过） 还有就是有一个细节，每次增加两个点，数组得开到操作数 $\times 2$ 。 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888 ...

题面大秦为你打开题目传送门 题目描述给一棵n个节点的树, 节点编号为1~n。 给定m条路径，问最多可以选多少条路径而且他们不经过同一个点。 题解这道题目很显而易见是一道贪心题目，我们借鉴类似于在区间上选择最多线段的题目的思路，不难想到策略：选 LCA 尽可能深的路径。 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152/** * @file HD ...

题面题目链接大秦 为你打开 题目传送门 题目翻译给一棵n个节点的树, 节点编号为1~n。 树上的结点要么是黑色，要么是白色，每次可以把连通的一种颜色变成另一种颜色。求至少要多少次，才能是整棵树变为一种颜色。 思路不难发现，如果我们把两个相邻的点是否相同作为边权，这道题目其实就是求出这棵树的直径上有多少种成对的不同的颜色。 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113/** * @file CF734E.cpp * @author Zhoumouren * @brief * @version 0.1 * @date 2024-08-22 * * @copyright C ...