T2 陌路寻诗礼

题目描述
帆巨所在的家乡的地图是一张有 $n$ 个节点 $m$ 条有向道路的有向图，每个节点都是一个城市，而帆巨所在的城市是 $1$ 号城市，并且 $1$ 号城市总是可以通过若干道路到达其他任何城市。
第 $i$ 条道路从 $x_i$ 号城市出发到达 $y_i$ 号城市，长度为 $z_i$。
帆帆现在要从他的 $1$ 号城市前往各个城市面基。
精通 spfa 算法的帆帆在面基的过程中自然会按照长度和最短的路径去其他城市。
但是帆帆有选择困难症，他希望从 $1$ 号城市到达每一座城市的最短路径都是唯一的，所以他决定施加魔法，改变所有道路的长度，具体地：
帆巨施加魔法后，对于每一条道路的长度，都可以 独立地 将其变成一个 $[1,k]$ 范围内的整数，其中 $k$ 是帆巨的魔法等级。
但帆巨所在的世界的地图和他的魔法等级一直在变，总共会变 $T$ 次，所以他希望你对 $T$ 次询问都给出一种构造方法使得帆巨不会纠结或者报告无解。

输入格式
第一行一个整数 $T$ 表示数据组数。
接下来 $T$ 组，每组先是三个整数 $n,m,k$，接着 $m$ 行描述有向道路 $(x_i,y_i)$。
不保证无自环无重边。
输出格式
对于每组数据，如果有解，第一行输出 Yes，第二行 $m$ 个数依次输出每条边的权值；如果没有解，一行输出 No。
本题采用 special judge 评测，也就是说，如果有多种可能的答案，你可以输出任意一种。
样例输入 #1

1
2
3
4
5
6
7
2
3 2 3
1 2
2 3
2 2 1
1 2
1 2

样例输出 #1

1
2
3
Yes
1 2
No

【样例解释】
对于第一组数据，$1$ 号点到达每个点的路径都是唯一，自然无论怎么设置边权，最短路都是唯一的。
对于第二组数据，因为 $k=1$，所以两条边的边权都只能设置为 $1$。$1$ 号点到 $2$ 号点的最短路长度为 $1$，走两条边都可以，所以不是唯一的。
【数据范围】
对于 $100\%$ 的数据，$n\ge 1$，$m\ge 0$，$1\le \sum n,\sum m\leq 3\times 10^5$，$1\leq k \leq 10^9$，$1\le x_i,y_i\le n$。

比赛一堆人说是随机乱搞ac的，留个坑等题解出了看看随机化怎么瞎搞做对的。
先考虑假设图是一颗树的情况，由于k必定大于1，可以发现一定是有解的，因为根（1号点）到其他点任意点的最短路径都只有一条。
考虑k等于1的时候，那么也就是说这个图边长只能是1，对于边长度固定的图，那么BFS找到的从起点结点到任意节点的路径都是最短路（也就是说边长固定的时候bfs可以直接代替优先队列跑dij）。所以可以直接bfs求最短路，并且由于最先出队的一定是最小的，然后发现如果1号点有从其他点到i的路径长度等于dist[i]那么一定是无解的。因为长度固定后能保证了跟i有关的结点路径长度越小的越先出队，所以如果想要更新dist[i]的唯一可能就是相等的时候所以一定是无解的。
k如果不是1那么显然之前k是1的时候有解那么k大于1也一定有解。关于k等于1时无解的情况，如果将与dist[i]相等的路径修改一下权值让他变成不是最短路即可，所以只要将他的路径变成2即可满足。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int n, m, k;

void solve() {
	cin >> n >> m >> k;
	int e[m + 5] {};
	vector<vector<PII>> edge(n + 1);
	for (int i = 1; i <= m; ++i) {
		int u, v;
		cin >> u >> v;
		edge[u].push_back({v, i});
	}
	int dist[n + 5] {};
	queue<int> q;
	q.push(1);
	for (int i = 1; i <= n; ++i) dist[i] = 2e9;
	dist[1] = 0;
	e[1] = 1;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (auto [v, p] : edge[u]) {
			if (dist[u] + 1 == dist[v])	e[p] = 2;
			if (dist[v] == 2e9) {
				dist[v] = dist[u] + 1;
				q.push(v);
			}
		}
	}
	for (int i = 1; i <= m; ++i)
		if (e[i] > k) return cout << "No" << endl, void();
	cout << "Yes" << endl;
	for (int i = 1; i <= m; ++i)
		cout << max(e[i], 1ll) << ' ';
	cout << endl;
}

T3 水影若深蓝

题目描述
当一切梦沉寂，他却遗忘了所有，只记得树上有 $n$ 个结点。
真的吗？似乎并没有，有 $m$ 件事情他一直牢记着，第 $i$ 件事情是：节点 $u_i$ 和 $v_i$ 在这棵深蓝之树上唯一的不重复经过某个点的路径恰好有两条边。
那么，你能否帮助帆帆想起来这棵深蓝之树的样子呢，如果有多个可能的，你只需要输出任意一种。
当然，帆帆也是会磨损的，因此当你发现无论如何都找不到满足帆帆这 $m$ 件事情的深蓝之树时，你需要报告无解。
大致意思就是给你树上的一些点对表示简单路径，并且给出的路径的长度都是2，构造一棵符合条件的树否则报告无解·。
输入格式
第一行一个正整数 $T$ 表示数据组数。
对于每组数据：
第一行两个非负整数 $n,m$ 表示树上的点数和帆帆记忆中事件个数。
接下来 $m$ 行，每行两个正整数 $u_i,v_i$ 表示一个事件。
输出格式
对于每组数据：

  • 若不存在符合条件的树，输出 No。
  • 否则，第一行输出 Yes，接下来 $n-1$ 行输出 $n-1$ 对正整数 $(u,v)$，表示你给出的树上的 $n-1$ 条边。

样例输入 #1

1
2
3
4
5
6
7
8
2
4 2
1 2
3 4
3 3
1 2
2 3
3 1

样例输出 #1

1
2
3
4
5
Yes
1 3
2 4
2 3
No

对于 $100\%$ 的数据，$1\le T\le 10^5$，$n\ge 1$，$m\ge 0$，$1\le \sum n\le 3\times 10^5$，$0\le \sum m\le 3\times 10^5$，$1\le u_i,v_i\le n$，$u_i\neq v_i$。
说是比T2简单……
一般来说图论的题目中含有距离是2的问题，奇偶性的问题往往要联想到二分图染色法之类的解法。
先根据点对建图，得到一些连通块，因为一个连通块之间相邻的边一定是不能相邻的，那么假设有多个连通块，只需要在不同连通块之间连边就可以保证每个点对都是距离为2。比如有连通块A和B，A中有点x，B中有点y，那么将A中所有除x的点都和y连边，将B中除y的所有点都和x连边，最后x和y连边。因为一共连了O(A)+O(B)-1条边且没有重边，所以这样就能保证构造出来的图一定是一棵树。
那么猜想一个连通块只在内部连边一定是不存在的，因为题目要求的是一棵树，树上距离是二的一定是二分染色后同色的部分的一些边。原树怎么都不可能形成两个以内的连通块，所以只有一个连通块的时候一定是不存在的情况。
所以建完图之后统计连通块的个数，如果大于1那么一定是有解的。输出的时候只需要找任意两个连通块将其他连通块中的点与他们相连即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
struct DSU {
	int n;
	vector<int> par, h;

	explicit DSU(int _n) : n(_n + 1), par(_n + 1), h(_n + 1) {
		for (int i = 1; i <= _n; ++i) par[i] = i;
	};

	int find(int x) {
		return par[x] != x ? par[x] = find(par[x]) : par[x];
	}

	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y)return;
		if (h[x] == h[y]) {
			h[x]++;
			par[y] = x;
		} else h[x] < h[y] ? par[x] = y : par[y] = x;
	}

	bool same(int x, int y) {
		return find(x) == find(y);
	}
};

int n, m;

void solve() {
	cin >> n >> m;
	DSU dsu(n);
	vector<vector<int>> edge(n + 1);
	for (int i = 1, u, v; i <= m; ++i) {
		cin >> u >> v;
//		edge[u].push_back(v),edge[v].push_back(u);
		dsu.unite(u, v);
	}
	for (int i = 1; i <= n; ++i) dsu.par[i] = dsu.find(i);
//	int cnt = 0;
	vector<int> root;
	for (int i = 1; i <= n; ++i)
		if (dsu.par[i] == i) root.push_back(i);
	if (si(root) == 1) return cout << "No" << endl, void();
	cout << "Yes" << endl;
	cout << root[0] << " " << root[1] << endl;
	for (int i = 1; i <= n; ++i) {
		if (i == root[0] || i == root[1]) continue;
		if (dsu.par[i] ^ root[0]) cout << root[0] << ' ' << i << endl;
		else cout << root[1] << ' ' << i << endl;
	}
}