自动搬运

查看原文

来自洛谷，原作者为

	CYJian 今日はこっちの地方はどしゃぶりの晴天でした，昨日もずっと暇で一日満喫してました

搬运于2025-08-24 22:25:30，当前版本为作者最后更新于2020-10-19 20:34:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

给定一棵 $n$ 个节点的树，给出 $m$ 条路径，试判断下面的命题是否成立：

$m$ 条路径中，任意两条路径的点集的交集为空，或者一个是另一个的子集。

$1 \leq n,m \leq 10^5$

吐槽

这个作业题怎么又是一个数据范围、时间复杂度和时限凑一起越看越离谱的题啊

先有一个 $10^6$ 的小常数线性复杂度题开 10s，这又整一个 $O(n \alpha(n))$ 的并查集题只开 $10^5$ 还开 3s 的...

题目解法

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

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

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

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

Code：

const int MAXN = 100010;

int tot;
int fi[MAXN];
int ne[MAXN << 1];
int to[MAXN << 1];

inline void Link(int u, int v) {
	tot++;
	to[tot] = v;
	ne[tot] = fi[u];
	fi[u] = tot;
}

int fa[MAXN];
int dep[MAXN];
int up[MAXN][20];

inline void dfs(int x, int la) {
	dep[x] = dep[la] + 1, up[x][0] = fa[x] = la;
	for(int i = 1; i < 20; i++)
		up[x][i] = up[up[x][i - 1]][i - 1];
	for(int i = fi[x]; i; i = ne[i]) {
		int u = to[i];
		if(u == la) continue;
		dfs(u, x);
	}
}

inline int LCA(int x, int y) {
	if(dep[x] < dep[y]) swap(x, y);
	int k = dep[x] - dep[y];
	for(int i = 0; i < 20; i++)
		if(k & (1 << i)) x = up[x][i];
	if(x == y) return x;
	for(int i = 19; ~i; --i)
		if(up[x][i] != up[y][i])
			x = up[x][i], y = up[y][i];
	return up[x][0];
}

struct Path {
	int u, v, lca, len, id;

	inline void init(int i) {
		id = i, u = ri, v = ri, lca = LCA(u, v);
		len = dep[u] + dep[v] - dep[lca] * 2;
	}

	friend bool operator < (Path a, Path b) { return a.len < b.len; }
}a[MAXN];

struct UFS {
	int fa[MAXN];
	int sz[MAXN];

	inline void init(int n) { for(int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1; }
	inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
	inline void Merge(int u, int v) {
		u = find(u), v = find(v);
		if(u == v) return ;
		fa[u] = v, sz[v] += sz[u];
	}
}ufs;

inline void Solve(Path x) {
	int u, d = dep[x.lca];
	u = ufs.find(x.u); while(dep[u] > d) ufs.Merge(u, fa[u]), u = ufs.find(u);
	u = ufs.find(x.v); while(dep[u] > d) ufs.Merge(u, fa[u]), u = ufs.find(u);
	if(x.len != ufs.sz[ufs.find(x.lca)] - 1) puts("No"), exit(0);
}

int main() {
	int n = ri, m = ri;
	for(int i = 1; i < n; i++) {
		int u = ri, v = ri;
		Link(u, v), Link(v, u);
	} dfs(1, 0);
	for(int i = 1; i <= m; i++) a[i].init(i);
	sort(a + 1, a + 1 + m), ufs.init(n);
	for(int i = 1; i <= m; i++) Solve(a[i]);
	puts("Yes");
	return 0;
}