VK Cup 2015 - Finals A. Matching Names
問題概要
n 個の名前と、n 個のペンネームが与えられる。これらを1対1対応させることを考える。
名前 a とペンネーム b をペアにした時の満足度を lcp(a, b) と定義する。
lcp(a, b) の総和が最大となるような、1対1対応を出力せよ。
1 <= n <= 10^5
文字列の長さの総和は 8 * 10^5
解法
lcp なので脳死で SA から攻めたくなりそうだが、lcp を Trie の上で考える視点も必要。
Trie における2文字列間の lcp は、LCA になる。
また、lcp(a, b) = (|a| + |b| - (|a| + |b| - 2 * lcp(a, b)) / 2 であることを考えると、lcp(a, b) の総和の最大化は（|a|, |b| が定数なので）以下のように言い換えられる。
木の上に n 頂点ずつ位置が与えられるので、それらをいい感じ組分けして最短距離の和の最小化をせよ
これは Trie を構築した後に dfs で下の方から貪欲的にペアを作っていけば達成できる。形式的に証明しなくても直感的にわかると思う。
これで計算量は O(total_length) となる。
ソースコード
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; struct alphabet_t { // default: 'a' - 'z' static constexpr int size = 26; static constexpr int char_to_index(char c) { assert('a' <= c && c <= 'z'); return c - 'a'; } static constexpr char index_to_char(int idx) { assert(0 <= idx && idx < size); return 'a' + idx; } }; template <typename Alpha> class trie { static constexpr int alpha_sz = Alpha::size; public: void insert(std::string const& s, int tag, int idx) { auto cur_node = this; for(int p = 0; p < static_cast<int>(s.size()); ++p) { const auto c = Alpha::char_to_index(s[p]); if(!cur_node->next[c]) cur_node->next[c] = std::make_unique<trie<Alpha>>(); cur_node = cur_node->next[c].get(); } cur_node->idxs[tag].push_back(idx); } // 本質 pair<int, array<vector<int>, 2>> solve(std::vector<pii>& ans) { auto res = make_pair(0, idxs); for(int i = 0; i < alpha_sz; ++i) { if(!next[i]) continue; auto ch = next[i]->solve(ans); res.second[0].insert(end(res.second[0]), begin(ch.second[0]), end(ch.second[0])); res.second[1].insert(end(res.second[1]), begin(ch.second[1]), end(ch.second[1])); res.first += ch.first; } while(!res.second[0].empty() && !res.second[1].empty()) { ans.emplace_back(res.second[0].back(), res.second[1].back()); res.second[0].pop_back(); res.second[1].pop_back(); } assert(res.second[0].empty() || res.second[1].empty()); res.first += res.second[0].size() + res.second[1].size(); return res; } private: std::array<std::unique_ptr<trie<Alpha>>, alpha_sz> next; array<vector<int>, 2> idxs; }; int main() { int n; cin >> n; trie<alphabet_t> t; int total_len = 0; for(int i = 0; i < 2 * n; ++i) { string s; cin >> s; t.insert(s, i >= n, (i >= n ? i - n + 1 : i + 1)); total_len += s.size(); } vector<pii> ans; cout << (total_len - t.solve(ans).first) / 2 << endl; for(auto& p : ans) { cout << p.first << " " << p.second << endl; } }
AOJ 0353 Sort
解法
とりあえず観察しないとよくわからない。
僕は観察してもよくわからなかったので、確実に言えることを探すことにした。
まず、一番小さい数は、左端に到達したら以降はもう動かない。その後に、二番目に小さい数が左から二番目の位置に到達したら以降は動かない。以下同様。
この事実を使うなら、まだ位置が確定していない値のうちで、最も小さい値が目的の位置に移動するまでにどのような変化が起こるか観察すべきだ。
そこで、次に位置を確定させる値に注目したとして、その値が適切な位置に移るまでを考える。
1 から i - 1 番目までは確定しているとする。次に注目するのは i 番目に小さい数である。その数が位置 j にあるとしよう。
この数が位置 i に到達するまでに発生するスワップ回数は、j - i 回である。これは考えてみると当然である。
これは、i から j 番目までの数字の並びは、スワップ回数に全く関係ないことを意味する。したがって、次に注目したい数が今どの位置にあるのかさえわかればよい、ということにほかならない。
この位置を効率よく探索するにはどうすればよいだろうか？要素がごっそり移り変わるので、単純なセグツリを使うということはできない（平衡二分木なら可能かも）。
これを考えるためには、後ろに追いやった数の並びについて、確実に言えることはなにかに注目しなければならない。
そして、いろいろ試すとわかるが、後ろに追いやられた値の全体としての並びは複雑でつらい気持ちになる。
しかしよく観察すると、後ろに追いやられた数の中で最小の値は、常に末尾に存在することに気がつく。
我々が必要なのは次に確定させたい値、それはつまり（選んでない中で）一番小さな値であり、その候補となる値以外の位置はどうでも良い。
そしてその候補となるのが、後ろに追いやった数の集合で最も小さい値である。
それらの位置は、前から位置を確定させるごとに後ろに追いやった数の集合の要素数さえわかれば、累積和の要領で求めることができる。
これまでの考察から、以下の解法を得る。
小さい値から順に注目し、前から位置を確定させていく。
このとき、注目した値を目的の位置に移るまでに後ろに追いやる数の集合をまとめ上げてしまう。この集合は、含まれる中で最も小さいものを得られるようなものにする（priority_queue など）。
注目した値が適切な位置に至るまでのスワップ回数は、まとめ上げた集合の要素数（の合計）に等しい。ただし注目している値自身は除く。
以降、この集合は分解することなく管理する。次に確定させる値のときも同様に、自身の位置から目的の位置までにある集合をまとめ上げ、自分以外を後ろに追いやるようにする。
これを最後の要素になるまで繰り返すと、答えが得られる。
集合のまとめ上げにマージテクを行えば、O(N(logN)^2) で解ける。
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; ++i) { cin >> a[i]; } { // compress auto b = a; sort(begin(b), end(b)); for(int i = 0; i < n; ++i) { a[i] = lower_bound(begin(b), end(b), a[i]) - begin(b); } } using S = priority_queue<int, vector<int>, greater<>>; function<void(S&, S&)> merge = [] (S& s1, S& s2) { if(s1.size() < s2.size()) swap(s1, s2); while(!s2.empty()) { s1.push(s2.top()); s2.pop(); } }; queue<shared_ptr<S>> que; for(int i = 0; i < n; ++i) { auto q = make_shared<S>(); q->push(a[i]); que.push(move(q)); } ll ans = 0; for(int i = 0; i < n; ++i) { auto s = que.front(); que.pop(); while(s->top() != i) { auto v = que.front(); que.pop(); merge(*s, *v); } s->pop(); ans += s->size(); que.push(s); } cout << ans << endl; }
感想
難しい。解説するのも（言葉だけだと）難しい。
かといって図を載せて解説する元気もなく…（公式解説を読んでください）。
よくこんな問題思いつくなあ。
AOJ 0323 Ruins
解法
二分探索するとよい。
海岸からの距離を y とすると、半円 i との交点の x 座標は、x[i] ± sqrt(r[i] * r[i] - y * y) となる。
これを区間と見て、すべての半円に対応する区間に共通区間があることが、その高さで共通領域がある条件である。
このギリギリを二分探索で調べて終わり。
ソースコード
#include <bits/stdc++.h> using namespace std; using ld = long double; int main() { int n; cin >> n; vector<ld> x(n), r(n); for(int i = 0; i < n; ++i) { cin >> x[i] >> r[i]; } auto check = [&] (ld y) { ld mini = -1e18, maxi = 1e18; for(int i = 0; i < n; ++i) { const auto d = sqrt(r[i] * r[i] - y * y); mini = max(mini, x[i] - d); maxi = min(maxi, x[i] + d); } return mini <= maxi; }; ld lb = 0, ub = *min_element(begin(r), end(r)); for(int lp = 0; lp <= 100; ++lp) { const auto mid = (lb + ub) / 2; (check(mid) ? lb : ub) = mid; } cout << setprecision(10) << fixed << lb << endl; }
Codeforces Round #316 (Div.2) E. Pig and Palindromes
解法
前と後ろの状態を同時に持たないことにはどうしようもなさそうだが、愚直に持つとオーダーが悪い。
よく考えると、現状態から i ステップ後の位置は、列か行の位置のどちらか一方を持てばもう一方も計算できる。
よって、結局先頭が何列目にいる、後ろが何列目にいるかで、DPテーブルとしては n * n の状態を持っておけば十分。
何ステップ後まで見るかだが、これは 2 * (i + 1) <= n + m - 2 となるまで遷移をくり返していけばいい（これは、互いがちょうど交わるか、交わらないギリギリのタイミングである）。
遷移するときは、遷移先が同じ文字であること、遷移した後の座標がもう一方を超えてしまって矛盾しないようにすることに注意する。
結局、計算量は O(n^3)、空間計算量は O(n^2) でできた。
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr int mod = 1e9 + 7; int main() { int n, m; cin >> n >> m; vector<string> v(n); for(int i = 0; i < n; ++i) { cin >> v[i]; } vector<vector<int>> dp(n, vector<int>(n)); constexpr int dx1[2] = {0, 1}, dy1[2] = {1, 0}; constexpr int dx2[2] = {0, -1}, dy2[2] = {-1, 0}; auto in_range = [n, m] (int y, int x) { return 0 <= y && y < n && 0 <= x && x < m; }; dp[0][n - 1] = v[0][0] == v[n - 1][m - 1]; for(int i = 0; 2 * (i + 1) <= n + m - 2; ++i) { vector<vector<int>> nxt(n, vector<int>(n)); for(int y1 = 0; y1 < n; ++y1) { for(int y2 = 0; y2 < n; ++y2) { const int x1 = i - y1, x2 = n + m - 2 - i - y2; if(!in_range(y1, x1) || !in_range(y2, x2)) continue; for(int d1 = 0; d1 < 2; ++d1) { for(int d2 = 0; d2 < 2; ++d2) { const int ny1 = y1 + dy1[d1], nx1 = x1 + dx1[d1]; const int ny2 = y2 + dy2[d2], nx2 = x2 + dx2[d2]; if(!in_range(ny1, nx1) || !in_range(ny2, nx2) || v[ny1][nx1] != v[ny2][nx2]) continue; if(ny1 > ny2 || nx1 > nx2) continue; (nxt[ny1][ny2] += dp[y1][y2]) %= mod; } } } } dp = move(nxt); } int ans = 0; for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) { (ans += dp[i][j]) %= mod; } } cout << ans << endl; }
感想
適当に書いたら一発で通ってビビった。
一方の情報からもう一方がわかるという性質からオーダーを落とす典型テクですね。
Codeforces Round #316 (Div.2) D. Tree Requests
解法
部分木の特定の高さのノードだけ取り出すのもオイラーツアーでできる。
この場合は高さごとにノードを管理すればよい。
各ノードが持つ区間は普通のオイラーツアーと同じで、各高さごとに持つデータは (今の index、文字を表す bit の xor sum) とする。
文字を表すビットとは、文字 c に対して 1 << (c - 'a') のことをいう。
どうしてこんなことをするかというと、今回制約が厳しいので 26 * m * log が間に合わないからである（log は区間の左端と右端を検索するのにどうしても必要）。
文字の状態を 32bit int で管理しておけば 26 が落とせるので嬉しい。
オイラーツアーのDFSで、頂点 v に到達したら data[height[v]] に ( l[v], data[height[v]].back() ^ (1 << (s[v] - 'a')) ) を追加する。xor の累積和。
各クエリに対しては、その区間の xor sum の popcount が 2 以上であれば回分にできないし、それ未満であれば回分にできる。
bit で26文字を圧縮して O(m * (log + 26)) で解けた。
ソースコード
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<vector<int>> g(n); for(int i = 1; i < n; ++i) { int p; cin >> p; g[p - 1].push_back(i); } string s; cin >> s; vector<int> bit(26); for(int i = 0; i < 26; ++i) { bit[i] = 1 << i; } vector<vector<pii>> hs(1 << 20, vector<pii>(1, make_pair(0, 0))); vector<int> l(n), r(n); { int cur = 1; function<void(int, int)> euler_tour = [&] (int v, int d) { l[v] = cur; hs[d].emplace_back(cur, hs[d].back().second ^ bit[s[v] - 'a']); for(auto to : g[v]) { euler_tour(to, d + 1); } r[v] = ++cur; }; euler_tour(0, 1); } for(int i = 0; i < m; ++i) { int v, h; cin >> v >> h; v--; const auto lb = lower_bound(begin(hs[h]), end(hs[h]), make_pair(l[v], -1)) - begin(hs[h]) - 1; const auto ub = lower_bound(begin(hs[h]), end(hs[h]), make_pair(r[v], -1)) - begin(hs[h]) - 1; const auto t = hs[h][ub].second ^ hs[h][lb].second; cout << ((t - (t & -t)) == 0 ? "Yes" : "No") << endl; } }
感想
26 を最初落とさなくてTLEしてしまった。
定番テクなのにすぐに思いつけなかったので反省。
AOJ 1383 Pizza Delivery
解法
始点および終点からの最短路を求めておく。それぞれ from_s, from_t とする。
次に s-t 最短路グラフを作る。このとき、グラフには s から t へ行くのに必要になるかもしれない辺のみを追加する（ここがサンプルにないので意外とハマりがち）。必要になりうる辺は、from_s[e.from] + e.cost + from_t[e.to] == from_s[t] となるような辺 e であるから、判定自体は簡単。
ある辺 e について、from_s[e.to] + e.cost + from_t[e.from] <= from_s[t] なら HAPPY か SOSO で、ここはそのまま出力して良い。
そうでないときに、最短路コストが増大するかどうかは、e が最短路グラフで橋になっているかどうかで判定できる。橋なら SAD でそうでなければ SOSO と出力すれば良い。（余計な辺が入っていると、この橋検出で本当は橋と判定すべきところを橋でないと判定してしまうのに注意。）
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr ll inf = 1e18; struct edge { int from, to; ll cost; }; using edges = vector<edge>; using graph = vector<edges>; void add_edge(graph& g, int from, int to, ll cost) { g[from].push_back(edge{from, to, cost}); } class lowlink { // multiple edges ok public: lowlink(graph const& g) : ord(g.size()), low(g.size()) { const int n = g.size(); std::vector<bool> visited(n); int cnt = 0; for(int i = 0; i < n; ++i) { if(!visited[i]) { dfs(g, i, -1, cnt, visited); } } } std::vector<int> get_articulation_points() const { return articulation_points; } std::vector<edge> get_bridges() const { return bridges; } bool is_bridge(int u, int v) const { if(ord[u] > ord[v]) std::swap(u, v); return ord[u] < low[v]; } private: void dfs(graph const& g, int v, int prev, int& cnt, std::vector<bool>& visited) { visited[v] = true; low[v] = ord[v] = cnt++; bool is_articulation = false; int cnt2 = 0, pcnt = 0; for(auto& e : g[v]) { if((e.to != prev || (e.to == prev && pcnt == 1)) && visited[e.to]) { low[v] = min(low[v], ord[e.to]); } else if(!visited[e.to]) { cnt2++; dfs(g, e.to, v, cnt, visited); low[v] = min(low[v], low[e.to]); if(prev != -1 && ord[v] <= low[e.to]) { is_articulation = true; } if(is_bridge(v, e.to)) { bridges.push_back(edge{min(v, e.to), max(v, e.to), e.cost}); } } pcnt += e.to == prev; } is_articulation |= (prev == -1 && cnt2 > 1); if(is_articulation) articulation_points.push_back(v); } private: std::vector<int> articulation_points; std::vector<edge> bridges; std::vector<int> ord, low; }; vector<ll> djikstra(graph const& g, int s) { const int n = g.size(); vector<ll> d(n, inf); d[s] = 0; priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> que; que.emplace(0, s); while(!que.empty()) { auto now = que.top(); que.pop(); const int v = now.second; if(d[v] < now.first) continue; for(auto& e : g[v]) { if(d[e.to] > d[v] + e.cost) { d[e.to] = d[v] + e.cost; que.emplace(d[e.to], e.to); } } } return d; } int main() { int n, m; cin >> n >> m; const int s = 0, t = 1; edges es; graph g(n), rg(n); for(int i = 0; i < m; ++i) { int a, b, c; cin >> a >> b >> c; es.push_back(edge{a - 1, b - 1, c}); add_edge(g, a - 1, b - 1, c); add_edge(rg, b - 1, a - 1, c); } auto from_s = djikstra(g, s), from_t = djikstra(rg, t); const ll dist = from_s[t]; graph sg(n); for(auto& e : es) { if(from_s[e.from] + e.cost + from_t[e.to] == dist) { add_edge(sg, e.from, e.to, e.cost); add_edge(sg, e.to, e.from, e.cost); } } lowlink helper(sg); for(auto& e : es) { if(from_s[e.to] + from_t[e.from] + e.cost <= dist) { if(from_s[e.to] + from_t[e.from] + e.cost < dist) { cout << "HAPPY" << endl; } else { cout << "SOSO" << endl; } } else if(from_s[e.from] + from_t[e.to] + e.cost == dist && helper.is_bridge(e.from, e.to)) { cout << "SAD" << endl; } else { cout << "SOSO" << endl; } } }
感想
本番で誤読して解くのが不可能な問題になっていたのを今でも覚えている…。
Codeforces Round #310 (Div.1) E - Case of Computer Network
解法
二重辺連結成分分解をしてくださいと書いてあるので、先にやっておく。
ただし、与えられるグラフは単純グラフとは限らないので、多重辺にも対応しておく。
するとグラフは森になるので、結局木の上で元の問題が解ければ良い。
ある辺について、どちらに向き付すべきかを考えよう。
（各）木について適当に根を決めて、根付き木にする。
ある頂点 v と、その親に伸びている辺について、その部分木に含まれる s[i] の数、d[i] の数、s[i] と d[i] の LCA の数をそれぞれ a, b, c とする（s[i], d[i], LCA の値として同じものがあっても、それらは何度も数える）。
すると、今注目している辺は、a - c が正のとき、上に伸びていなければならないし、逆に b - c が正のとき、下に伸びていなければならない。
これは、v の部分木内で完結している s[i], d[i] のペアの数が部分木に含まれる LCA の数に対応していることを考えれば容易にわかる。
これらがともに正となるとき、与えられた条件を満たす向きづけは存在しない。それ以外のときは、向き付が存在する。
ソースコード
#include <bits/stdc++.h> using namespace std; struct edge { int from, to; }; using edges = std::vector<edge>; using graph = std::vector<edges>; void add_edge(graph& g, int from, int to) { g[from].push_back(edge{from, to}); g[to].push_back(edge{to, from}); } class lowlink { public: lowlink(graph const& g) : ord(g.size()), low(g.size()) { const int n = g.size(); std::vector<bool> visited(n); int cnt = 0; for(int i = 0; i < n; ++i) { if(!visited[i]) { dfs(g, i, -1, cnt, visited); } } } std::vector<edge> get_bridges() const { return bridges; } bool is_bridge(int u, int v) const { assert(0 <= u && u < (int)ord.size() && 0 <= v && v < (int)ord.size()); if(ord[u] > ord[v]) std::swap(u, v); return ord[u] < low[v]; } private: void dfs(graph const& g, int v, int prev, int& cnt, std::vector<bool>& visited) { visited[v] = true; low[v] = ord[v] = cnt++; int cnt2 = 0, pcnt = 0; for(auto& e : g[v]) { if((e.to != prev || (e.to == prev && pcnt == 1)) && visited[e.to]) { low[v] = min(low[v], ord[e.to]); } else if(!visited[e.to]) { cnt2++; dfs(g, e.to, v, cnt, visited); low[v] = min(low[v], low[e.to]); if(is_bridge(v, e.to)) { bridges.push_back(edge{min(v, e.to), max(v, e.to)}); } } pcnt += e.to == prev; } } private: std::vector<edge> bridges; std::vector<int> ord, low; }; // require: lowlink class biconnected_component { public: biconnected_component(graph const& g_) : g(g_), helper(g_), belongs_(g_.size(), -1) { for(auto&& b : helper.get_bridges()) { add_component(b.from), add_component(b.to); } add_component(0); } graph build() { // if not connected, result is forest graph res(cmps.size()); auto bridges = helper.get_bridges(); for(auto& b : bridges) { add_edge(res, belongs(b.from), belongs(b.to)); } return res; } int belongs(int u) const { assert(0 <= u && u < (int)belongs_.size()); return belongs_[u]; } private: void fill_component(int c, int u) { cmps[c].emplace_back(u); belongs_[u] = c; for(auto& e : g[u]) { if(belongs_[e.to] >= 0 || helper.is_bridge(u, e.to)) continue; fill_component(c, e.to); } } void add_component(int u) { if(belongs_[u] >= 0) return; cmps.emplace_back(); assert(cmps.size() >= 1u); fill_component(cmps.size() - 1, u); } private: graph g; lowlink helper; std::vector<int> belongs_; std::vector<std::vector<int>> cmps; }; class lowest_common_ancestor { public: lowest_common_ancestor(graph const& g/* int root*/) : n(g.size()), log_n(std::ceil(std::log2(g.size())) + 1), parent(log_n, std::vector<int>(n, -1)), depth_(n) { for(int i = 0; i < n; ++i) { if(parent[0][i] == -1) dfs(g, i, -1, 0); } for(int k = 0; k + 1 < log_n; ++k) { for(int v = 0; v < n; ++v) { if(parent[k][v] < 0) parent[k + 1][v] = -1; else parent[k + 1][v] = parent[k][parent[k][v]]; } } } int query(int u, int v) const { if(depth_[u] > depth_[v]) { std::swap(u, v); } for(int k = 0; k < log_n; ++k) { if((depth_[v] - depth_[u]) >> k & 1) { v = parent[k][v]; } } if(u == v) { return u; } for(int k = log_n - 1; k >= 0; --k) { if(parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } private: void dfs(graph const& g, int v, int p, int d) { parent[0][v] = p; depth_[v] = d; for(auto& e : g[v]) { if(e.to != p) { dfs(g, e.to, v, d + 1); } } } private: int const n, log_n; std::vector<std::vector<int>> parent; std::vector<int> depth_; }; class union_find { public: union_find(int n) : par(n, -1) {} int root(int x) { return par[x] < 0 ? x : par[x] = root(par[x]); } bool same(int x, int y) { return root(x) == root(y); } void unite(int x, int y) { x = root(x), y = root(y); if(x == y) return; if(par[x] > par[y]) swap(x, y); par[x] += par[y]; par[y] = x; } private: vector<int> par; }; int main() { int n, m, q; cin >> n >> m >> q; graph g(n); for(int i = 0; i < m; ++i) { int v, u; cin >> v >> u; add_edge(g, v - 1, u - 1); } vector<int> s(q), d(q); for(int i = 0; i < q; ++i) { cin >> s[i] >> d[i]; s[i]--, d[i]--; } biconnected_component bicc(g); auto t = bicc.build(); const int tn = t.size(); lowest_common_ancestor lca(t); union_find uf(tn); for(auto& es : t) { for(auto& e : es) { uf.unite(e.from, e.to); } } vector<int> sum1(tn), sum2(tn), sum3(tn); for(int i = 0; i < q; ++i) { s[i] = bicc.belongs(s[i]), d[i] = bicc.belongs(d[i]); if(!uf.same(s[i], d[i])) { cout << "No" << endl; return 0; } sum1[s[i]] += 1, sum2[d[i]] += 1; sum3[lca.query(s[i], d[i])] += 1; } vector<bool> visited(tn); function<bool(int, int)> dfs = [&] (int v, int p) { bool res = true; visited[v] = true; for(auto& e : t[v]) { if(e.to == p) continue; res &= dfs(e.to, v); sum1[v] += sum1[e.to], sum2[v] += sum2[e.to], sum3[v] += sum3[e.to]; } return res & (sum1[v] - sum3[v] <= 0 || sum2[v] - sum3[v] <= 0); }; bool ans = true; for(int i = 0; i < tn; ++i) { if(visited[uf.root(i)]) continue; ans &= dfs(uf.root(i), -1); } cout << (ans ? "Yes" : "No") << endl; }
感想
単純グラフじゃないのはいいとして、連結である保証すら無いのでいじわるだなあと思った（本質じゃないんだから手を抜いてくれても良いんじゃないかなあ）。
ライブラリがないと実装するの大変そう。ICPCだったら最悪。
後で気がついたけど、テストケースがダメダメっぽい。部分木の総和を求め忘れてても通ってしまっていた。
