DFS

题意：~ 思路：给定一个n个点，n-1条边，问添加少的边使原图变成一个双连通图。因为给定的就是一棵树，所以问题简单了很多。 #include <bits/stdc++.h> using namespace std; const int N = 100050; vector<int> g[N]; vector<int&...

题目链接：点我~~ 题意：给定一棵树，每次询问一个集合，问所有不在这个集合的点两两 LCA (可以相同)的并集大小。 思路：实际上就是对于每个被删掉的点，check 一下是不是除了一个子树之外的点都被删掉了。那么对于每个被删掉的点的连通块，从最高点开始 dfs 就行。 #include <bits/stdc++.h> using namespa...

题目链接：点我~~ 题意：给出一棵n个结点的树和一个数k, 每个节点上有权值ai, 问有多少个有序对(u,v)满足u是v的祖先, 且au*av≤k. 思路：从根开始dfs, 用线段树维护当前节点u到根的节点权值序列, 数据很大,需要离散化,然后就查询小于等于k/au的数的个数. 之后把au插入, 然后继续查找子节点,回溯的时候再删去该节点。其实就是查找每个节...

题目链接：点我~~ 题意：~~ 思路：首先注意到任意两条边的边权是不一样的，由此得知最小生成树是唯一的，最小生成树既然 是唯一的，那么期望其实也就是唯一的，不存在什么最小期望。求完最小生成树之后，接下 来的问题就可以转换成在最小生成树上求任意两点之间距离的平均值，对于每条边，统计所 有的路径用到此边的次数，也就是边的两端的点数之积。那么这条边的总贡献就是次数...

新增加的泡泡如果跟周围同色的泡泡相连个数>=3，他们就会爆炸，还有不是头顶第一排相连的，也会爆炸，先处理下跟新增加的泡泡相连的泡泡，然后再统计头顶相连的泡泡。。奇偶行泡泡个数不一样，所以要分开处理。。 #include<iostream> #include<cstdio> #include<string> #incl...