P9194
P9194 [USACO23OPEN] Triples of Cows P 题解
直接建边边数过多,不好处理。我们可以考虑建一些虚点,让 \(u_i\) 和 \(n+i\) 连边,\(v_i\) 和 \(n+i\) 连边。设这些新连的点为白点,与白点有连边的点在原图中一定相连,并且一定是一棵树。删除操作相当于把 \(u\) 的子白点连到他的父白点上,使用并查集维护即可。 这时再考 ......
P9194 [USACO23OPEN] Triples of Cows P 题解
Description 给定一棵初始有 \(n\) 个点的树。 在第 \(i\) 天,这棵树的第 \(i\) 个点会被删除,所有与点 \(i\) 直接相连的点之间都会两两连上一条边。你需要在每次删点发生前,求出满足 \((a,b)\) 之间有边,\((b,c)\) 之间有边且 \(a\not=c\) ......