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

Minimize pairwise connectivity after removal of a node

Revision en1, by tahuruzzoha, 2023-11-01 21:00:19

Can anyone please help me in one problem?

Problem: You are given an undirected connected graph, and Q queries, in each query you will be given a vertex 'v' and output for each query should be v(v-1)/2 with remains component after removal of vertex 'v'. When removing node v, the subtree of v's child will be disconnected from the rest of the graph and also separate from the main graph. Each of the part of the graph after removing one node perform this v(v-1)/2 where v is the count of the total connected component this part.

Now you have to minimize the pairwise connectivity after removing each node.

nodes <= 20^5; queries <= 20^5 (Queries are independent).

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English tahuruzzoha 2023-11-11 15:27:34 10
en2 English tahuruzzoha 2023-11-11 15:24:29 1271
en1 English tahuruzzoha 2023-11-01 21:00:19 725 Initial revision (published)