D. A Wide, Wide Graph

1n1 \to n 이 아닌 kk1n1 \leftarrow n 으로 진행된다고 하자.

그럼 순서가 역이 되었기 때문에 그래프가 점점 끊어지는 것이 아닌 이어지는 것이 된다.

트리의 지름 DD 가 있고, 그 때의 두 정점을 u1,u2u_1, u_2 라 하자.

결국 u1u2u_1 u_2 가 처음에 이어지고 계속 하나의 큰 컴포넌트로 연결되는 모습을 띌 것이다.

따라서 정답은 특정 시점에 이 컴포넌트의 크기를 SS라고 하면 Min(N,NS+1)\text{Min}(N, N-S+1) 이 정답이다.

k=D+1k=D+1 \sim 라면 항상 정답은 NN 이다. 아무 정점끼리도 이어질 수 없기 때문이다.

k=Dk=D 부터 u1,u2u_1,u_2 를 포함해서 다른 정점들이 이어질 수 있다.

우린 u1,u2u_1, u_2 부터 시작하는 최단경로 두 개를 구한다.

그리고 모든 노드들에 대해서 u1,u2u_1, u_2 에서의 최단경로 중 더 큰 값이 kk 일 때 그래프에 포함된다고 정의할 수 있다.

왜냐면 두 개의 트리의 지름을 구성하는 노드의 성질에 의해 모든 정점들이 가장 긴 거리를 갖는 정점이 그 두 정점 중 하나이기 때문이다.

DSU는 안써도 풀 수 있다.

void solve() {  
   int n;  
   cin >> n;  
   vvi edges(n);  
   for (int i = 0; i < n - 1; i++) {  
      int u, v;  
      cin >> u >> v, u--, v--;  
      edges[u].pb(v), edges[v].pb(u);  
   }  
   DSU dsu(n);  
  
   vi dist(n);  
   function<void(int, int, vi &)> fn = [&](int cur, int p, vi &dist) -> void {  
      for (int to: edges[cur]) {  
         if (to == p) continue;  
         dist[to] = dist[cur] + 1;  
         fn(to, cur, dist);  
      }  
   };  
   fn(0, -1, dist);  
   int u1 = maxi(dist);  
   dist[u1] = 0;  
   vi dist1(n), dist2(n);  
   fn(u1, -1, dist1);  
   int u2 = maxi(dist1);  
   fn(u2, -1, dist2);  
   int dia = maxe(dist1);  
   vi ans(n + 1);  
  
   for (int i = n; i >= dia + 1; i--) ans[i] = n;  
   vvi enter(n + 1);  
   // k = 트리의 지름일 때 , 처음으로 u1, u2가 들어온다.  
   for (int i = 0; i < n; i++) {  
      if (i == u1 || i == u2) continue;  
      int t = max(dist1[i], dist2[i]);  
      enter[t].pb(i);  
   }  
   dsu.merge(u1, u2);  
   for (int i = dia; i >= 1; i--) {  
      for (int j: enter[i]) {  
         if (!dsu.is_merged(u1, j)) {  
            dsu.merge(u1, j);  
         }  
      }  
      ans[i] = n - dsu.size(u1) + 1;  
   }  
   for (int i = 1; i <= n; i++)cout << ans[i] << ' ';  
}

Comments