Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

tahuruzzoha's blog

By tahuruzzoha, history, 9 months ago, In English

Problem: You are given an undirected connected graph and a set of Q queries. Each query involves removing a vertex 'v' from the graph. After removing vertex 'v', the subtree of 'v's child is disconnected from the rest of the graph and is treated as a separate component. For each such component, calculate the value v(v-1)/2, where v is the count of vertices in that component.

The goal is to minimize the pairwise connectivity after removing each node. The pairwise connectivity is the sum of v(v-1)/2 for all components resulting from the removal of the node 'v'.

Input: A connected undirected graph with nodes (vertices) and edges. Q queries, each specifying a vertex 'v' to be removed.

Output: For each query, output the minimum pairwise connectivity after removing the specified vertex 'v' according to the rules defined above.

Constraints: The number of nodes (vertices) in the graph is less than or equal to 20^5. The number of queries is less than or equal to 20^5. Queries are independent of each other.

Example: Input: Graph: {1-2, 1-3, 2-4, 2-5, 3-6} Queries: Q1(1), Q2(2), Q3(3)

Output: After removing vertex 1: Pairwise connectivity = 4 After removing vertex 2: Pairwise connectivity = 4 After removing vertex 3: Pairwise connectivity = 2

Note: The provided example is for illustration purposes only and may not represent the actual solution to the problem. The actual solution depends on the specific structure of the given graph and queries.

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by tahuruzzoha (previous revision, new revision, compare).

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i agree