洛谷 P6963

不难发现，包含关系只可能是短的路径被长的路径包含。

那么我们考虑按照路径长度从小到大，一条一条路径边加入边判断。

考虑先将树上的所有边断开，每加入一条路径的时候就将这条路径上包含的边加入，用并查集维护连通块的点数。不难发现，如果加入一条路径后，这条路径所在连通块的点数与当前加入的这条路径上的点数不同时，就必然存在一条路径，与当前加入的这条路径不满足题目所给命题，此时可以判定不成立了。如果加入后点数相符合，那么当前就没有问题。

如果将所有路径都加入了还没出现问题，那么这个命题就可以确定为正确的了。

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, m, t;
int head[N], ver[N*2], nxt[N*2], cnt;
int fa[N][18], dep[N];

void add(int u, int v) {
	ver[++cnt] = v, nxt[cnt] = head[u], head[u] = cnt;
}

void dfs(int u, int Fa) {
	for (int i = head[u]; i; i = nxt[i]) {
		int v = ver[i];
		if (v == Fa) continue;
		fa[v][0] = u, dep[v] = dep[u] + 1;
		for (int j = 1; j <= t; ++j)
			fa[v][j] = fa[fa[v][j - 1]][j - 1];
		dfs(v, u);
	}
}

int LCA(int x, int y) {
	if (dep[x] > dep[y]) swap(x, y);
	for (int i = t; ~i; --i)
		if (dep[x] <= dep[fa[y][i]]) y = fa[y][i];
	if (x == y) return x;
	for (int i = t; ~i; --i)
		if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
	return fa[x][0];
}

struct Path {
	int x, y, lca, len;
	
	void init() {
		scanf("%d%d", &x, &y), lca = LCA(x, y);
		len = dep[x] + dep[y] - 2 * dep[lca];
	}
	bool operator < (const Path &rhs) const {
		return len < rhs.len;
	}
} a[N];

struct DSU {
	int fa[N], siz[N];
	
	void init() { for (int i = 1; i <= n; ++i) fa[i] = i, siz[i] = 1; }
	int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
	void merge(int x, int y) { x = find(x), y = find(y); if (x == y) return; fa[x] = y, siz[y] += siz[x]; }
} dsu;

void solve(Path cur) {
	int x = dsu.find(cur.x), y = dsu.find(cur.y), lca = cur.lca, len = cur.len;
	while (dep[x] > dep[lca]) dsu.merge(x, fa[x][0]), x = dsu.find(x);
	while (dep[y] > dep[lca]) dsu.merge(y, fa[y][0]), y = dsu.find(y);
	if (len != dsu.siz[dsu.find(lca)] - 1) printf("No"), exit(0);
}

int main() {
	scanf("%d%d", &n, &m), t = (log(n) / log(2)) + 1;
	for (int i = 1, u, v; i < n; ++i) scanf("%d%d", &u, &v), add(u, v), add(v, u);
	dep[1] = 1, dfs(1, 0);
	for (int i = 1; i <= m; ++i) a[i].init();
	sort(a + 1, a + m + 1), dsu.init();
	for (int i = 1; i <= m; ++i) solve(a[i]);
	printf("Yes");
	return 0;
}