//3解法間のストレステスト #include #include #include #include #include using namespace std; mt19937 mt(252521); //乱数生成器, メルセンヌ・ツイスタ //Union Find Tree struct UF { int n; vector par; int merge_cnt; void init(int n) { this->n = n; par.resize(n); for (int i = 0; i < n; i++) { par[i] = i; } merge_cnt = 0; } int root(int x) { if (par[x] == x) { return x; } return par[x] = root(par[x]); } bool same(int x, int y) { return root(x) == root(y); } void merge(int x, int y) { x = root(x); y = root(y); if (x != y) { par[x] = y; merge_cnt++; } } }; //テストケース構造体 class Testcase { private: vector a, b; public: int n; vector> edge_to; string color; void generate(int n) { UF uf; uf.init(n); edge_to.resize(n); this->n = n; while (uf.merge_cnt < n - 1) { int u = mt() % n; int v = mt() % n; if (uf.same(u, v) == false) { uf.merge(u, v); a.push_back(u); b.push_back(v); edge_to[u].push_back(v); edge_to[v].push_back(u); } } for (int i = 0; i < n; i++) { if (mt() % 100 < 50) { color += 'b'; } else { color += 'w'; } } } void input() { cin >> n; edge_to.resize(n); for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; a--; b--; edge_to[a].push_back(b); edge_to[b].push_back(a); } int m; cin >> m; color = ""; for (int i = 0; i < n; i++) color += 'w'; for (int i = 0; i < m; i++) { int v; cin >> v; v--; color[v] = 'b'; } } void print() { cout << n << endl; for (int i = 0; i < n - 1; i++) { cout << a[i] << " " << b[i] << endl; } cout << color << endl; } }; //Solverの基底クラス class Solver { protected: int n; vector edge_to[200000]; string color; void input(Testcase &testcase) { n = testcase.n; for (int i = 0; i < n; i++) { edge_to[i] = testcase.edge_to[i]; } color = testcase.color; } virtual vector solve(Testcase &testcase) = 0; }; //ナイーブ解1:O(N^2) class NaiveSolver1 : public Solver { private: vector operate(int v) { vector blacks; if (color[v] == 'b') { blacks.push_back(v); } for (int nv : edge_to[v]) { //vの隣接頂点nv if (color[nv] == 'b') { blacks.push_back(nv); } } for (int b : blacks) { color[b] = 'w'; } return blacks; } bool is_danger(int v) { if (color[v] == 'b') { return true; } for (int nv : edge_to[v]) { if (color[nv] == 'b') { return true; } } return false; } int calc() { int ret = 0; for (int v = 0; v < n; v++) { //頂点vについて危険かを調べる if (is_danger(v)) { ret++; } } return ret; } void revert(vector change_vs) { for (int v : change_vs) { color[v] = 'b'; } } public: vector solve(Testcase &testcase) { input(testcase); vector ans; for (int v = 0; v < n; v++) { vector change_vs = operate(v); //色を変更した頂点リストを返す ans.push_back(calc()); revert(change_vs); } return ans; } }; //ナイーブ解2: O(N^2), ランダムグラフのとき高速 class NaiveSolver2 : public Solver { private: int cnt_black[200000]; //cnt_black[v] = 頂点v自身・vの隣接頂点のうち黒であるものの個数 int safe_cnt; //safe_cnt = cnt_black[v]が0であるような頂点vの個数 void calc_init() { safe_cnt = 0; for (int v = 0; v < n; v++) { cnt_black[v] = 0; if (color[v] == 'b') { cnt_black[v]++; } for (int nv : edge_to[v]) { if (color[nv] == 'b') { cnt_black[v]++; } } if (cnt_black[v] == 0) { safe_cnt++; } } } vector operate(int v) { vector blacks; if (color[v] == 'b') { blacks.push_back(v); } for (int nv : edge_to[v]) { if (color[nv] == 'b') { blacks.push_back(nv); } } for (int u : blacks) { //頂点uについて、uから距離1以内の頂点xのcnt_black[x]を1減らす cnt_black[u]--; if (cnt_black[u] == 0) { safe_cnt++; } for (int x: edge_to[u]) { cnt_black[x]--; if (cnt_black[x] == 0) { safe_cnt++; } } } return blacks; } void revert(vector change_vs) { for (int v : change_vs) { if (cnt_black[v] == 0) { safe_cnt--; } cnt_black[v]++; for (int x : edge_to[v]) { if (cnt_black[x] == 0) { safe_cnt--; } cnt_black[x]++; } } } public: vector solve(Testcase &testcase) { input(testcase); calc_init(); vector ans; for (int v = 0; v < n; v++) { vector change_vs = operate(v); ans.push_back(n - safe_cnt); revert(change_vs); } return ans; } }; //想定解: O(N), デバッグ済み class FastSolver : public Solver { private: int black[200000]; //black[v] = vと隣接する黒頂点の個数 int to_bfs[200000]; int parent_bfs[200000]; int child_bfs_l[200000], child_bfs_r[200000]; //[l, r] int safe_bfs[200001]; //safe_bfs[bfsId] = BFS順序でbfsId番の頂点について操作をおこなった場合の、危険でない頂点の個数 void init_member() { for (int i = 0; i < n; i++) { black[i] = 0; to_bfs[i] = 0; parent_bfs[i] = 0; child_bfs_l[i] = 0; child_bfs_r[i] = 0; safe_bfs[i] = 0; } safe_bfs[n] = 0; } void bfs(int root_v) { vector used(n, false); queue que; int t = 0; for (int bfs_v = 0; bfs_v < n; bfs_v++) { parent_bfs[bfs_v] = -1; child_bfs_l[bfs_v] = -1; child_bfs_r[bfs_v] = -1; } to_bfs[root_v] = t; t++; que.push(root_v); used[root_v] = true; while (!que.empty()) { int v = que.front(); que.pop(); for (int nv : edge_to[v]) { if (used[nv]) { continue; } to_bfs[nv] = t; parent_bfs[t] = to_bfs[v]; if (child_bfs_l[to_bfs[v]] == -1) { child_bfs_l[to_bfs[v]] = t; } //最初見る子のbfsIdになる child_bfs_r[to_bfs[v]] = t; //最後見る子のbfsIdになる t++; que.push(nv); used[nv] = true; } } } //safe_bfs[l, r) += 1, を階差数列上でおこなう void add(int l, int r) { if (debug_flag) { printf("safe_bfs[%d, %d] += 1\n", l, r); } safe_bfs[l]++; safe_bfs[r + 1]--; } void add_near(int v) { int bfs_v = to_bfs[v]; int l = child_bfs_l[bfs_v]; int r = child_bfs_r[bfs_v]; int p = parent_bfs[bfs_v]; //v自身 add(bfs_v, bfs_v); //vの子[l, r] (vが葉でないとき) if (l != -1) { add(l, r); } //vの親(vが根でないとき) if (p != -1) { add(p, p); } } public: bool debug_flag; FastSolver() { debug_flag = false; } vector solve(Testcase &testcase) { input(testcase); init_member(); for (int v = 0; v < n; v++) { for (int nv : edge_to[v]) { if (color[nv] == 'b') { black[v]++; } } } bfs(0); if (debug_flag) { cout << " id | to_bfs, parent_bfs, child_bfs_l, child_bfs_r" << endl; cout << "--------------------------------------------------" << endl; for (int v = 0; v < n; v++) { printf("%3d | %6d, %10d, %11d, %11d\n", v, to_bfs[v], parent_bfs[to_bfs[v]], child_bfs_l[to_bfs[v]], child_bfs_r[to_bfs[v]]); } } for (int v = 0; v < n; v++) { //頂点vが安全になる操作uをカウントアップ if (debug_flag) { printf("\n"); printf("black[%d] = %d, color[%d] = %c\n", v, black[v], v, color[v]); } if (black[v] == 0) { if (color[v] == 'w') { //u: 全頂点, imos法で区間[0, n)に加算 add(0, n - 1); } else { add_near(v); //v自身とvの隣接頂点に加算 } } else if (black[v] == 1) { int x; for (int nv : edge_to[v]) { //v=0,..,Nにおけるループ回数の和は次数の和 = 2N - 2. if (color[nv] == 'b') { x = nv; break; } } if (color[v] == 'w') { add_near(x); //x自身とxの隣接頂点に加算、ここの高速化がデカい! } else { int bfs_x = to_bfs[x]; int bfs_v = to_bfs[v]; add(bfs_x, bfs_x); add(bfs_v, bfs_v); } } else { //操作uで頂点vを安全にするには、u = vとするしかない! int bfs_v = to_bfs[v]; add(bfs_v, bfs_v); } } //累積和を取る for (int i = 0; i < n; i++) { safe_bfs[i + 1] += safe_bfs[i]; } //答えを出力する if (debug_flag) { puts(""); } vector ans; for (int v = 0; v < n; v++) { if (debug_flag) { printf("safe_bfs[%d] = %d\n", v, safe_bfs[v]); } int bfs_v = to_bfs[v]; ans.push_back(n - safe_bfs[bfs_v]); } return ans; } }; NaiveSolver1 solver1; NaiveSolver2 solver2; FastSolver solver3; bool stress_test(int caseNum, int N, Testcase &return_case) { for (int T = 0; T < caseNum; T++) { int n = N; Testcase testcase; testcase.generate(n); vector ans1 = solver1.solve(testcase); vector ans3 = solver3.solve(testcase); if (ans1 != ans3) { cout << "Wrong Answer[" << T << "]" << endl; cout << "Testcase (0-idx):" << endl; testcase.print(); cout << endl; cout << "Different Answer (0-idx):" << endl; for (int i = 0; i < n; i++) { if (ans1[i] != ans3[i]) { cout << i << " : " << ans1[i] << ", " << ans3[i] << endl; } } return_case = testcase; return true; } } cout << "Accepted" << endl; return false; } int main() { /*Testcase testcase; bool is_wrong = stress_test(1000, 15, testcase); if (is_wrong) { solver3.debug_flag = true; solver3.solve(testcase); }*/ Testcase testcase; testcase.input(); vector ans = solver3.solve(testcase); for (int i = 0; i < ans.size(); i++) cout << ans[i] << endl; }