B. Diameter of Graph

图论，构造

题意：

有n个结点，m条边，两点间距离定义为两点间最短路的长度，问前面给出的条件能否构成一个无向联通图，使得两点间距离小于k-1，不存在自环和重边。

思路：

先考虑正好能构成图的边界条件：这个可以很简单想到，边的个数一定是在\([n-1,\ \frac{n*(n-1)}{2}]\)间的，可以自己构造几个图找规律就不给出证明了。

那么我们需要考虑的就是，怎么样才能让当前能被满足的边数最短呢？先考虑边数等于\(n-1\)的情况，我们会发现，菊花图会让当前边数下的两点间距离最短（其实是看了题解的，想不到呜呜呜，浅浅记录一下），此时的最短距离为2。

那么继续向下想，如果我们要继续在菊花图的基础上向图里加边，我们每次连接距离大于1的结点，让二者间距离变为1。那么什么时候最大距离会发生变化呢？就是当边数加到\(\frac{n*(n-1)}{2}\)的时候，且我们无法再向图里加任何一条边。此时的最短距离为1。

也就是说，在边数小于\(\frac{n*(n-1)}{2}\)之前，最短距离都为2，在达到\(\frac{n*(n-1)}{2}\)之后，最短距离为1。特别的，在这里需要特判当结点数为1的时候，此时图中没有任何边，最短距离为0。

此外，这题还需特别注意，题目给出的要求是两点间距离小于k-1，也就是说，两点间距离小于等于k-2。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
#define endl "\n"
const int N = 2e5 + 10;
ll n, m, k; 
void solve(){
	cin >> n >> m >> k;
	if(m < n - 1 || m > n * (n - 1) / 2){
		cout << "NO\n";
	}
	else if(n == 1){//注意要先判断结点为1的情况
		if(k >= 2) cout << "YES\n";
		else cout << "NO\n";
	}
	else if(m == n * (n - 1) / 2){
		if(k >= 3) cout << "YES\n";
		else cout << "NO\n";
	}
	else{
		if(k >= 4) cout << "YES\n";
		else cout << "NO\n";
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int _;
	cin >> _;
	while(_ --){
		solve();
	}
	return 0;
}

Don’t Really Like How The Story Ends

图论，dfs

题意：

初始有n个点和m条边，问如果需要按结点编号进行dfs搜索，最少需要添加多少条边。（dfs过程中优先走未走过的编号最小的结点）

思路：

首先，对于当前已有的点，我们需要思考如何通过遍历去让它在恰当的时候被访问到。在这里引用来自学长的题解思路，写得非常清晰明了。

设now为当前结点，nxt为now + 1也即是下一个结点

如果now和nxt直接相连，那么可以直接到nxt，不需要添加额外的边（因为之前一定是从1到now进行遍历，所以我们也不需要考虑小于nxt的边）
如果now和nxt不直接相连
- 如果now接下来还有比nxt大的结点和它相连，根据dfs的性质我们不走nxt就一定会走更大的结点，与题意不符合，所以我们需要添加一条边从now到nxt，以保证我们接下来走nxt
- 如果now是叶子节点，那么对于dfs来说，我们遍历到叶子节点就会向上返回回溯走另一条路。所以我们就直接返回，看上面的父节点是否能满足我们的条件。

特别的，如果当前走到根结点了，也就是说没有父亲结点返回了，那么我们就需要建立一条1到nxt的边。在实现的过程中需要注意，因为在判断是否添加边的情况时，我们是在判断当前结点是否存在更大的边，所以我们需要在根节点上加一个指向n+1的边，以处理上面的特别情况。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
#define endl "\n"
#define int long long
const int N = 1e6 + 10;
int n, m, h[N];

void solve(){
	cin >> n >> m;
	vector<vector<int>> num(n + 1);
	for(int i = 1; i <= m; i ++){
		int x, y;
		cin >> x >> y;
		num[x].push_back(y);
		num[y].push_back(x);
	}
	num[1].push_back(n + 1);
	int now = 2, cnt = 0;
	function<void(int)> dfs = [&](int u) -> void{
		if(u == n + 1) return ;
		sort(num[u].begin(), num[u].end());
		for(auto v : num[u]){
			while(now <= v){
				if(v == now){
					now ++;
					dfs(v);
				}
				else{
					cnt ++;
					now ++;
					dfs(now - 1);
				}
			}
		}
	};
	dfs(1);
	cout << cnt << endl;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while(t --)
		solve(); 
	return 0;
}

J. Mex Tree

图论

题意：

一棵有\(n\)个结点的树，每个点的权值为\(v_i\)，权值为\(0,...,n-1\)的全排列，问是否存在联通子树使得其\(Mex\)值为\(0,...,n\)，输出最大联通子块大小。

思路：

首先，对于\(Mex\)运算，我们很简单就能想到，对于一个连通块，只需要检查是否存在0~k-1的编号的点就可以了。如果暴力的思路就是每次对编号为k的结点依次查找它的每一棵子树，如果有子树符合条件就输出子树大小。

但是，很明显这题按上面的暴力思路会tle，我们需要思考如何去优化查询的过程。

一个我自己想出来的小总结（不知道正确性只提供一个思考方向）。

对于树来说，当它是没有固定遍历顺序（或者说需要从任意一个节点向外搜索的时候）的时候，我们最好先指定一个根节点（通常设为0或是1），再去思考题目所需要的性质或是处理方法

根据我们上面的小贴士，继续思考怎么去处理这道题：假设我们从权值为0的点开始遍历，那么对于权值为k的节点，如果需要满足\(Mex\)=k，一定要取到它上面的子树（因为上方的子树里一定有0），抛弃下面的子树。而如果下面的子树里有比k小的元素，我们在选上面的子树的时候就一定无法取到满足要求的连通块。

那么问题就到了我们要怎么去记录才能通过查询快速找到子树里不存在比k小的元素呢？最终得出的思路是，记录每一棵子树中最小的元素，查询的时候去查询每一棵子树的最小元素，如果比当前节点小，那么就不能被满足。

特别的，对于\(Mex\)=0的情况，我们只需要找到其最大的那棵子树然后输出就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define endl "\n"
const int N=1e6+10;
int n,minn[N],h[N],idx,num[N],son[N],fa[N];
map<int,int> mp;

struct type{
	int nxt,to;
}tr[N<<1];

void add(int u,int v){
	idx++;
	tr[idx].nxt=h[u];
	tr[idx].to=v;
	h[u]=idx;
}

void dfs(int fu,int u){
	fa[u]=fu;
	for(int t=h[u];t;t=tr[t].nxt){
		if(tr[t].to==fu) continue;
		dfs(u,tr[t].to);
		son[u]+=son[tr[t].to];
		minn[u]=min(minn[u],minn[tr[t].to]);
	}
}

void solve(){
	cin>>n;
	int st=0;
	for(int i=1;i<=n;i++){
		son[i]=1;
		cin>>num[i];
		minn[i]=num[i];
		mp[num[i]]=i;
		if(num[i]==0) st=i; 
	}
	for(int i=2;i<=n;i++){
		int v;
		cin>>v;
		add(i,v);
		add(v,i);
	}
	for(int t=h[st];t;t=tr[t].nxt){
		dfs(st,tr[t].to);
	}
	int maxx=0;
	for(int t=h[st];t;t=tr[t].nxt){
		maxx=max(maxx,son[tr[t].to]);
	}
	cout<<maxx<<" ";
	for(int i=1;i<n;i++){
		int u=mp[i];
		bool flag=true;
		for(int j=h[u];j;j=tr[j].nxt){
			if(fa[u]==tr[j].to) continue;
			if(minn[tr[j].to]<i){
				flag=false;
				cout<<"0 ";
				break; 
			}
		}
		if(flag) cout<<n-son[u]<<" ";
	}
	cout<<n<<endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	solve();
	return 0;
}

再放个队友的代码，他写的比我精简很多（晕）

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<functional>
#include<cmath>
#include<queue>
#include<string>
#include<fstream>
#include<set>
typedef long long ll;
using namespace std;
struct node {
	int x, v;
};

void solve() {
	int n;
	cin >> n;
	vector<int>num(n + 1);
	vector<int>ans(n + 1);
	vector<int>sz(n + 1);
	ans[n] = n;
	int root = 0;
	for (int i = 1; i <= n; i++) {
		cin >> num[i];
		if (num[i] == 0)root = i;
	}
	int u;
	vector<vector<int>>edge(n + 1, vector<int>());
	for (int i = 2; i <= n; i++) {
		cin >> u;
		edge[u].push_back(i);
		edge[i].push_back(u);
	}
	function<int(int, int)>dfs = [&](int p, int fa) {
		int mi = num[p];
		sz[p] = 1;
		for (auto x : edge[p]) {
			if (x != fa) {
				mi = min(mi, dfs(x, p));
				sz[p] += sz[x];
				if (p == root) {
					ans[0] = max(ans[0], sz[x]);
				}
			}
		}
		if (mi < num[p] && p != root)ans[num[p]] = 0;
		else if (p != root)ans[num[p]] = n - sz[p];
		return mi;
	};
	dfs(root, root);
	for (int i = 0; i <= n; i++) {
		cout << ans[i] << ' ';
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	solve();
	return 0;
}