T1NFLSOJP2023050961捉迷藏首先只需要考虑所有叶子，只要每个叶子都连向了另一个距离超过\(2\)的叶子，则符合要求。距离超过\(2\)等价于在不同的父亲下。则问题变为一堆点，每个点有颜色，同色点间没有边，异色点间两两有边，求最大匹配。结论：设点最多的颜色\(c\)有\(x\)个点，若

T1洛谷P3479GAS-FireExtinguishers考虑贪心，从叶子往上，对于每个点能不放就不放，实在要放了再放。要知道一个点能不能不放，需要知道子树中最深的还没有被覆盖的点的距离。记\(f[i][j]\)为\(i\)子树中距离\(i\)为\(j\)的点有多少点没有被覆盖。一个点放了灭火器之后可以覆

T1TopcoderSRM579div1Medium-TravellingPurchasingMan发现行动肯定是从当前点沿最短路走到目标然后等开门然后买然后去下一个目标。所以先对每个关键点为原点跑一遍最短路，然后状压一下，\(dp[S][i]\)表示已经买了\(S\)集合，当前在\(S\)中的\(i\)。转移就枚举目的地，看过

T1TopcoderSRM567div1Medium-StringGame首先字母表定了之后两个人一定都会把字符串按字母表排序。对于这样的两个字符串，只需要数出两个串中每种字母分别有多少个，然后对着计数数组按字母表顺序比过去，在第一个不一样处更大的字典序小。因此先数一数每个字符串中每个字符出现

T1TopcoderSRM583div1Medium-TurnOnLamps发现取反一条路径相当于把两个端点到根的路径分别取反。所以只要考虑到根的情况。设\(f[i]\)表示\(i\)子树内所有边都合法的最小操作次数，则每个点只要把所有儿子的\(f\)加过来然后看到儿子的每条边是否合法即可。代码#i

T1洛谷P2047社交网络暴力Floyd跑出每两个点间最短路及其条数，然后暴力枚举算。代码#include<iostream>#include<string.h>#include<iomanip>#include<queue>#defineintlonglongusingnamespacestd;intn,m;intdist[105][105];intcnt[105][105];sign

由于博客园存在关站风险，文章以后同步发在这里，可能会有更好的阅读体验。首先我们分析一下，如果我们已经知道了要走哪些点，我们可以怎么做。考虑将\(a_i,b_i\)之间连边，发现题目可以被转化为给定一个图，要求对于每条边将其一个顶点染色，问最多能将多少个点染色。于是我们对于每个连

第一次AKabc，写篇题解记录一下。原题传送门分析发现实际上是要求删去每个绿点之后会多出几个连通块。发现这跟割点的定义很像，于是考虑建图，在相邻的绿点之间连边。然后就只要知道每个点到底被包含在几个点双里。我们使用圆方树，此时就只需要统计每个点的度数就可以了。代码#in

题目链接：https://www.luogu.com.cn/problem/P2860题目大意：给定一个无向连通图，求至少加几条边，能使其变成一个边双连通图。解题思路：边双连通分量缩点后计算度数为\(1\)的节点个数，假设有\(cnt\)个，则答案为\((cnt+1)/2\)。示例程序：#include<bits/stdc++.h>usingnamespacestd;

题目链接：https://www.luogu.com.cn/problem/P2860题目大意：给定一个无向连通图，求至少加几条边，能使其变成一个边双连通图。解题思路：边双连通分量缩点后计算度数为\(1\)的节点个数，假设有\(cnt\)个，则答案为\((cnt+1)/2\)。示例程序：#include<bits/stdc++.h>usingnamespac

题意：安排计划，有4种约束方式，给出你这些时间的n个约束..如果计划是可行的，求出每一件事发生的最早时间..否则输出“impossible”..①.FAFaba要在b完成后完成..②.FASaba要在b开始前完成..③.SASaba要在b开始前开始..④.SAFaba要在b结束前开

解决问题解不等式方程。形如\(x_i\lex_j+w\)ps.等式可以化为两个不等式解决方法。相当于每条有向边松弛后的柿子。所以跑最短路即可。但有可能负权，而且要判无解（有

求\(n\)个点的树上对于每个点距离小于\(k\)的点的数量（边权均为\(1\)）。\(n\leq5\times10^5，k\leq10\)。设\(f[u][i]\)表示距离\(u\)点\(i\)距离以内并且

每条边有边权\(l\)和值\(e\)，求满足\(e_ie_{i+1}=a^k\)的连续边的边权和最大值。\(n\leq10^5,m\leq2\times10^5,w\leq10^5,k\leq10\)。一道很有意思的题，用到了很