int N, M, INF = 10000000, vis[100001], dis[100001], U[100001], V[100001]; vector<pii> G[100001]; void solve() { rep(i, N)G[i].clear(), vis[i] = 0; // Union-Find木 UnionFind uf(N); // クエリの種類 // 0: 返答可能な質問 // INF: 返答不可能な質問 //</pii>…

性質を満たす木が存在する必要十分条件は、すべての頂点についてクエリに現れた回数が偶数であることである。 (1)すべて偶数回の出現だった場合 すべてのクエリについて 辺(a[i], b[i])で2頂点をつなぐ。ただし、a[i], b[i]がすでに同じ連結成分内にある場合…

k回目の魔法で部屋を開いた状態にする操作は、k+1回目以降の移動にしか影響しない。 よって、魔法を以下のように捉え直す。 1回目の魔法は移動のみ 2回目の魔法は部屋を開く操作ののち、移動 2回目以降の操作はK個以下の部屋を開き、K個以下のマスを移動でき…

int main(){ ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; vector<set<int> > G(N); rep(i, N - 1) { int a, b; cin >> a >> b; --a; --b; G[a].insert(b); G[b].insert(a); } /* 完全マッチングが存在するか判定 木なので、葉は必ずその親とペアにな</set<int>…