Codeforces Round 862 (Div. 2) - D. A Wide, Wide Graph (1800)

D. A Wide, Wide Graph

$1 \to n$ 이 아닌 $k$ 가 $1 \leftarrow n$ 으로 진행된다고 하자.

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

트리의 지름 $D$ 가 있고, 그 때의 두 정점을 $u_1, u_2$ 라 하자.

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

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

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

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

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

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

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

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] << ' ';  
}