dfs文章列表
[luoguP3565] [POI2014]HOT-Hotels（dfs）
传送门 三点在树上距离相等的情况只有一种，就是以某一个点为中心，三个点到这个点的距离相等。 所以直接枚举每个点作为中心，dfs这个中心的子树，根据乘法原理统计答案即可。 时间复杂度 O(n 2 ) (...dfs
[luoguP2680] 运输计划（lca + 二分 + 差分）
传送门 暴力做法 50 ~ 60 枚举删边，求最大路径长度的最小值。 其中最大路径长度运用到了lca 我们发现，求lca的过程已经不能优化了，那么看看枚举删边的过程能不能优化。 先把边按照权值排序，然...stl,tarjan,lca,dfs,倍增
[luoguP1433] 吃奶酪（DP || Dfs）
传送门 深搜加剪纸可A（O(玄学) 1274ms） ——代码 1 #include cmath 2 #include cstdio 3 #include iostream 4 5 int n; 6 d...DP,dfs
[luoguP1351] 联合权值（Dfs）
传送门 距离为2的点会产生权值，第一问，只需要在dfs的时候把一个点相邻的点都处理出来就行。 具体处理方式看代码，然而这样只处理了一遍，最后在乘2就好了。 第二问只需要处理一个点相邻的点中最大的和次大...dfs,模拟
[BZOJ1179] [Apio2009]Atm（tarjan缩点 + spfa）
传送门 题意 N个点M条边的有向图 每个点有点权 从某一个结点出发 问能获得的最大点权和 一个点的点权最多被计算一次 N=500000 M=500000 思路 先tarjan缩点，然后就形成一个dag...DP,最短路,dfs,spfa,stl
[luoguP2982][USACO10FEB]慢下来Slowing down（dfs序 + 线段树）
传送门 这个题显然可以用树链剖分做。 然而线段树也能做。 每个点都对它的子树有贡献，所以先求一边 dfs序，然后直接在 dfs序 中搞 线段树 就行。 ——代码 1 #include cstdio 2...线段树,dfs序,dfs,树链剖分
[luoguP2444] [POI2000]病毒（AC自动机 + dfs）
传送门 先把所有串建一个AC自动机， 如果要找一个不包含任意一个串的串， 说明这个串一直在AC自动机上匹配但匹配不到， 也就是说，匹配时除去val值为1的点，除去fail指针指向val值为1的点，是否...AC自动机,dfs
[luoguP3178] [HAOI2015]树上操作（dfs序 + 线段树 || 树链剖分）
传送门 树链剖分固然可以搞。 但还有另一种做法，可以看出，增加一个节点的权值会对以它为根的整棵子树都有影响，相当于给整棵子树增加一个值。 而给以某一节点 x 为根的子树增加一个权值也会影响当前子树，节...线段树,树链剖分,dfs序,dfs
[luoguP2420] 让我们异或吧（dfs + 异或的性质）
传送门 因为异或满足结合律和交换律。 a^b^b=a 所以这个题直接求根节点到每个点路径上的异或值。 对于每组询问直接输出根到两个点的异或值的异或的值。 ——代码 1 #include cstdio ...dfs
NOIP2009T3最优贸易（Dfs + spfa）
洛谷传送门 看到这个题，原本想先从后往前dfs，求出能到终点的点，再在这些点里从前往后spfa，用一条边上的两个城市的商品价格的差来作边权，实施过后，发现图中既有负边权，又有回路，以及各种奇奇怪怪的东...最短路,spfa,dfs
香港服务器 数据安全 数据库 美国服务器 云服务器 IT DDoS Linux Windows 虚拟化