[Here](https://mirror.codeforces.com/gym/608931) is the contest link.↵
↵
#### [A. Funny Game](https://mirror.codeforces.com/gym/608931/problem/A)↵
↵
<spoiler summary = "Hint">↵
1 sounds like the minimum value we can get. Why? Is it always true?↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
When n ≤ 2, we can do nothing.↵
When n ≥ 3, since , n - 1 isn't a divisor of n, so we can choose it and get 1 as the result.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
n = int(input())↵
↵
if n == 2:↵
print(2)↵
else:↵
print(1)↵
↵
```↵
</spoiler>↵
↵
↵
#### [B. Metshaf Exchange](https://mirror.codeforces.com/gym/608931/problem/B)↵
↵
<spoiler summary="Problem Summary">↵
You're given a permutation p of n elements. Each person i gives their item to p[i]. The process continues daily. For each person, compute the number of days it takes to get their own item back.↵
↵
This is equivalent to finding the length of the cycle each element is part of↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 1">↵
Can u check the constraints↵
↵
<spoiler summary="answer">↵
Constraints:↵
1 ≤ n ≤ 200↵
1 ≤ q ≤ 200↵
This makes O(n²) solutions feasible.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
**Brute Force Solution**↵
↵
<spoiler summary="Solution 1">↵
For each element, follow the permutation until it loops back to the original position↵
</spoiler>↵
↵
↵
<spoiler summary="Code 1">↵
```python3↵
def check(p, n):↵
res = [0] * n↵
for i in range(n):↵
cnt = 1↵
cur = p[i] - 1↵
while cur != i:↵
cur = p[cur] - 1↵
cnt += 1↵
res[i] = cnt↵
return res↵
↵
q = int(input())↵
for _ in range(q):↵
n = int(input())↵
p = list(map(int, input().split()))↵
print(*check(p, n))↵
↵
```↵
</spoiler>↵
↵
<spoiler summary="Solution 2">↵
For each element, follow the permutation until it loops back to the original position↵
</spoiler>↵
↵
↵
<spoiler summary="Code 2">↵
↵
```python3↵
↵
from collections import defaultdict, deque↵
↵
q = int(input())↵
for _ in range(q):↵
n = int(input())↵
p = list(map(int, input().split()))↵
graph = defaultdict(list)↵
for i in range(1, n + 1):↵
graph[i].append(p[i - 1])↵
↵
ans = []↵
for i in range(1, n + 1):↵
queue = deque([i])↵
visited = {i}↵
days = 0↵
while queue:↵
node = queue.popleft()↵
for neighbour in graph[node]:↵
if neighbour not in visited and neighbour != node:↵
visited.add(neighbour)↵
queue.append(neighbour)↵
days += 1↵
ans.append(days + 1)↵
print(*ans)↵
↵
↵
```↵
</spoiler>↵
↵
**Optimal Solution**↵
↵
<spoiler summary = "Hint">↵
Can we see that every element belonging to the same cycle actually forms a group together?↵
↵
<spoiler summary="answer">↵
Yes, exactly! Each cycle in the permutation represents a group of elements that are all connected through mappings. So we can use Disjoint Set Union (DSU) to group these elements together. Once grouped, we can easily determine the size of each cycle by checking the size of each group.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
To solve the problem efficiently, we can use the **Disjoint Set Union (DSU)** data structure, also known as **Union-Find**, which is ideal for managing groups of connected elements. The core idea is to treat each cycle in the permutation as a group and then track these groups as we process the permutation.↵
↵
The DSU allows us to efficiently group elements together and later find the size of each group. For this problem, we will use **path compression** in the `find` operation to speed up future queries, and **union by size** to ensure we merge smaller groups into larger ones, which optimizes the union operation.↵
↵
We start by initializing the DSU for each test case, where each element is its own parent. Then, for each element in the permutation, we union the element with the one it points to. After processing all elements, we can use the `find` operation to determine the root of each element's cycle and then count the size of each cycle by checking the size of the connected group it belongs to.↵
↵
This approach ensures that we can efficiently handle the problem even with large inputs, as the time complexity for both union and find operations is nearly constant, due to the inverse Ackermann function, which grows extremely slowly. Thus, the solution is both time-efficient and space-efficient for large values of `n`.↵
↵
Time Complexity:↵
O(n * α(n)) per test case, where n is the number of elements and α(n) is the inverse Ackermann function. For practical input sizes, α(n) is very small, often treated as a constant.↵
↵
Space Complexity:↵
O(n) for storing the parent, rank (or size), and other DSU-related arrays.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
↵
input = sys.stdin.readline↵
↵
# Input helpers↵
I = lambda: int(input())↵
ILT = lambda: list(map(int, input().split()))↵
↵
class DSU:↵
def __init__(self, n):↵
self.rank = [0] * (n + 1)↵
self.parent = list(range(n + 1))↵
self.size = [1] * (n + 1)↵
↵
def find(self, node):↵
if node == self.parent[node]:↵
return node↵
stack = []↵
while node != self.parent[node]:↵
stack.append(node)↵
node = self.parent[node]↵
for n in stack:↵
self.parent[n] = node↵
return node↵
↵
def Sunion(self, u, v): # Union by size↵
rep_u = self.find(u)↵
rep_v = self.find(v)↵
if rep_u == rep_v:↵
return↵
if self.size[rep_u] < self.size[rep_v]:↵
self.parent[rep_u] = rep_v↵
self.size[rep_v] += self.size[rep_u]↵
else:↵
self.parent[rep_v] = rep_u↵
self.size[rep_u] += self.size[rep_v]↵
↵
def Runion(self, u, v): # Union by rank↵
rep_u = self.find(u)↵
rep_v = self.find(v)↵
if rep_u == rep_v:↵
return↵
if self.rank[rep_u] < self.rank[rep_v]:↵
self.parent[rep_u] = rep_v↵
elif self.rank[rep_v] < self.rank[rep_u]:↵
self.parent[rep_v] = rep_u↵
else:↵
self.parent[rep_v] = rep_u↵
self.rank[rep_u] += 1↵
↵
def solve():↵
n = int(input())↵
p = list(map(int , input().split()))↵
uf = DSU(n)↵
for i in range(n):↵
uf.Sunion(p[i], i + 1)↵
print(*[uf.size[uf.find(i)] for i in range(1, n + 1)])↵
↵
for _ in range(int(input())):↵
solve()↵
↵
```↵
</spoiler>↵
↵
↵
↵
#### [C. Destroy](https://mirror.codeforces.com/gym/608931/problem/C)↵
↵
<spoiler summary="Hint 1">↵
Instead of simulating destruction from the beginning, try **reversing** the process.↵
Imagine you start with an **empty array**, and at each step you **restore** one element.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
When you restore an element, you want to **join it with its neighbors** (if they are already restored), to form a **continuous segment**.↵
To track segments and their sums efficiently, you can use a structure that merges and finds connected components.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Use a **disjoint set** (also called union-find) to keep track of connected segments and their total sums.↵
Each restored position is its own segment initially. Then, if neighboring positions are restored, you merge them and update the total.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Here's the idea:↵
↵
- Process the array in **reverse destruction order** (i.e., imagine "restoring" the numbers).↵
- Keep track of which positions are active using a union-find structure.↵
- For each newly added number:↵
- Set its value.↵
- If neighbors are already restored, merge the segments.↵
- Update the **maximum segment sum** seen so far.↵
- Store the maximum sum after each restoration. At the end, reverse the answer to match the original destruction order.↵
↵
This approach works in **O(n * α(n))** where α is the inverse Ackermann function — effectively constant.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
↵
# Union-Find (Disjoint Set Union) with segment sum tracking↵
class Dsu:↵
def __init__(self, size):↵
self.parent = [i for i in range(size + 1)] # parent[i] = leader of the set containing i↵
self.size = [1 for i in range(size + 1)] # size[i] = size of set with leader i↵
self.total = [-1 for i in range(size + 1)] # total[i] = sum of the segment with leader i↵
↵
def find(self, x):↵
# Path compression to find leader↵
if x != self.parent[x]:↵
self.parent[x] = self.find(self.parent[x])↵
return self.parent[x]↵
↵
def union(self, x, y):↵
# Merge two segments↵
px = self.find(x)↵
py = self.find(y)↵
↵
if px != py:↵
# Union by size (smaller into larger)↵
if self.size[px] > self.size[py]:↵
px, py = py, px↵
self.parent[px] = py↵
self.size[py] += self.size[px]↵
self.total[py] += self.total[px] # Update total segment sum↵
↵
↵
def solve():↵
n = int(sys.stdin.readline().strip())↵
nums = [0] + list(map(int, sys.stdin.readline().strip().split())) # 1-indexed↵
queries = list(map(int, sys.stdin.readline().strip().split())) # destruction order↵
↵
dsu = Dsu(n)↵
ans = [0] # answer after 0 restorations↵
maxi = 0 # current maximum segment sum↵
↵
# Process in reverse: simulate "restoring" elements↵
for val in queries[::-1]:↵
dsu.total[val] = nums[val] # restore the value at position `val`↵
↵
# Try to join with the left neighbor↵
if val - 1 > 0 and dsu.total[val - 1] > -1:↵
dsu.union(val - 1, val)↵
↵
# Try to join with the right neighbor↵
if val + 1 <= n and dsu.total[val + 1] > -1:↵
dsu.union(val + 1, val)↵
↵
# Get the sum of the segment that includes this restored value↵
cursum = dsu.total[dsu.find(val)]↵
maxi = max(maxi, cursum)↵
ans.append(maxi) # save current max after this restoration↵
↵
# Remove the last dummy value and reverse to match destruction order↵
ans.pop()↵
for val in ans[::-1]:↵
print(val)↵
↵
```↵
</spoiler>↵
↵
↵
#### [D. Masha and The Bear](https://mirror.codeforces.com/gym/608931/problem/D)↵
↵
<spoiler summary = "Solution 1">↵
<p>↵
Let’s use graph to represent the facts given in the problem. A node in the graph represents a snack flavour. Every guest likes exactly two different snack flavours, so an edge can be used to represent a guest by connecting two nodes(snack flavours) that the guest likes.↵
</p>↵
↵
<p>↵
For each connected component element, the first person will always eat two snacks. Then we can find an order in which every other person eats one until all the snacks are eaten. So the number of happy guests is ,<b>N — 1</b> where <b>N</b> is the number of nodes in that connected component. It’s guaranteed that such a sequence of guests always exist and there is no better way to make more guests happier. ↵
</p>↵
↵
<p>↵
So, a simple <b>dfs/bfs</b> can be used to find the answer. We can find the total number of happy guests by traversing each connected component separately. Then the number of unhappy guest will be the total number of guests minus the total number of happy guests.↵
</p>↵
↵
<p><b>Time and space complexities</b></p>↵
<ul>↵
<li>↵
<b> Time Complexity: O(n)</b>↵
</li>↵
<li>↵
<b> Space Complexity: O(n)</b>↵
</li>↵
</ul>↵
</spoiler>↵
↵
↵
<spoiler summary="Code 1">↵
```↵
from collections import defaultdict, deque↵
↵
n, k = map(int, input().split())↵
graph = defaultdict(list)↵
for _ in range(k):↵
l, r = map(int, input().split())↵
graph[l].append(r)↵
graph[r].append(l)↵
↵
def bfs(start):↵
q = deque([start])↵
visited.add(start)↵
↵
count = 0↵
while q:↵
node = q.popleft()↵
count += 1↵
↵
for child in graph[node]:↵
if child not in visited:↵
q.append(child)↵
visited.add(child)↵
↵
return count↵
↵
↵
happy = 0↵
visited = set()↵
for i in range(1, n + 1):↵
if i not in visited:↵
happy += bfs(i) - 1↵
↵
print(k - happy)↵
↵
↵
```↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution 2">↵
↵
The problem can be reduced to finding the number of edges that form cycles in a graph where nodes are snacks and edges are guests (connecting their two favorite flavors). In a tree (a connected component without cycles), we can always order guests so that no one is sad each guest arrives when at least one favorite snack is still available. However, cycles force at least one sad guest because, no matter the order, some guest will find both snacks already eaten. For this we can use DSU.↵
↵
Each time we try to connect two already linked nodes, it means we’ve found a cycle, and thus a sad guest. The total number of such edges gives the minimum sad guests, as trees contribute zero and each cycle adds exactly one unavoidable sad guest.↵
↵
<p><b>Time and space complexities</b></p>↵
<ul>↵
<li>↵
<b> Time Complexity: O(k)</b>↵
</li>↵
<li>↵
<b> Space Complexity: O(k)</b>↵
</li>↵
</ul>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code 2">↵
```↵
class UnionFind:↵
def __init__(self, size):↵
self.parent = {i:i for i in range(size)}↵
self.sizes = {i:1 for i in range(size)}↵
↵
def find(self, x):↵
while x != self.parent[x]:↵
self.parent[x] = self.parent[self.parent[x]]↵
x = self.parent[x]↵
return x↵
↵
def union(self, x, y):↵
root1 = self.find(x)↵
root2 = self.find(y)↵
↵
if root1 == root2:↵
return False↵
↵
if self.sizes[root2] > self.sizes[root1]:↵
root1,root2 = root2,root1↵
↵
self.parent[root2] = root1↵
self.sizes[root1] += self.sizes[root2]↵
↵
return True↵
↵
↵
n, k = map(int, input().split())↵
↵
answer = 0↵
↵
dsu = UnionFind(n + 1) ↵
↵
for _ in range(k):↵
u, v = map(int, input().split())↵
↵
if not dsu.union(u, v):↵
answer += 1↵
↵
↵
print(answer)↵
↵
```↵
</spoiler>↵
↵
↵
#### [E. Wide, Wide Graph](https://mirror.codeforces.com/gym/608931/problem/E)↵
↵
<spoiler summary = "Hint"> What if we think in reverse: from a graph with no edges to adding edges based on distance? </spoiler>↵
↵
↵
<spoiler summary = "Solution"> ↵
We are given a tree, and for each integer $k$ from 1 to $n$, we must count the number of connected components in a graph $Gk$, where an edge exists between two nodes only if their distance in the tree is at least $k$.↵
Instead of checking all pairs of nodes for each $k$, which would be too slow $O(n^2)$, we take advantage of tree properties:↵
↵
- In a tree, there's a unique path between any two nodes. So we can define the "distance" easily using BFS or DFS.↵
↵
- Let’s fix a special node the farthest node from any random node (say, node $0$). From that, perform BFS to find ↵
the node furthest from it this gives one endpoint of the diameter. Do a final BFS from this endpoint to get the actual diameter and each node’s distance from it. We then compute the maximum distance for each node from either endpoint of the diameter. If the maximum distance of a node is less than $k$, then this node becomes isolated in $Gk$ since no other node is at distance ≥ $k$. ↵
↵
Hence, for each $k$, we count how many nodes become isolated (i.e., their max distance $k$, and increment the number of components accordingly.↵
This gives an $O(n)$ solution using just a few BFS traversals and basic counting.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python3↵
from collections import deque↵
↵
def bfs(tree, start):↵
n = len(tree)↵
dist = [-1] * n↵
dist[start] = 0↵
q = deque([start])↵
while q:↵
node = q.popleft()↵
for neighbor in tree[node]:↵
if dist[neighbor] == -1:↵
dist[neighbor] = dist[node] + 1↵
q.append(neighbor)↵
return dist↵
↵
def main():↵
n = int(input())↵
↵
tree = [[] for _ in range(n)]↵
for _ in range(n - 1):↵
u, v = map(int, input().split())↵
# Convert to 0-based index ↵
u -= 1↵
v -= 1↵
tree[u].append(v)↵
tree[v].append(u)↵
↵
# Step 1: BFS from arbitrary node (0) to find one endpoint of diameter↵
d1 = bfs(tree, 0)↵
far1 = d1.index(max(d1))↵
↵
# Step 2: BFS from far1 to get distances and find farthest point (diameter)↵
d2 = bfs(tree, far1)↵
diameter = max(d2)↵
far2 = d2.index(diameter)↵
↵
# Step 3: BFS from far2 to get second set of distances↵
d3 = bfs(tree, far2)↵
↵
# For each node, take the maximum distance to either end of diameter↵
max_dist = [max(d2[i], d3[i]) for i in range(n)]↵
↵
# Count how many nodes have max_dist < k↵
isolated_count = [0] * (n + 2)↵
for d in max_dist:↵
isolated_count[d] += 1↵
↵
result = [1] # G_1 has 1 component (the whole tree)↵
for k in range(2, n + 1):↵
if k > diameter:↵
result.append(n)↵
else:↵
result.append(result[-1] + isolated_count[k - 1]) ↵
↵
print(' '.join(map(str, result)))↵
↵
main()↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
#### [A. Funny Game](https://mirror.codeforces.com/gym/608931/problem/A)↵
↵
<spoiler summary = "Hint">↵
1 sounds like the minimum value we can get. Why? Is it always true?↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
When n ≤ 2, we can do nothing.↵
When n ≥ 3, since , n - 1 isn't a divisor of n, so we can choose it and get 1 as the result.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
n = int(input())↵
↵
if n == 2:↵
print(2)↵
else:↵
print(1)↵
↵
```↵
</spoiler>↵
↵
↵
#### [B. Metshaf Exchange](https://mirror.codeforces.com/gym/608931/problem/B)↵
↵
<spoiler summary="Problem Summary">↵
You're given a permutation p of n elements. Each person i gives their item to p[i]. The process continues daily. For each person, compute the number of days it takes to get their own item back.↵
↵
This is equivalent to finding the length of the cycle each element is part of↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 1">↵
Can u check the constraints↵
↵
<spoiler summary="answer">↵
Constraints:↵
1 ≤ n ≤ 200↵
1 ≤ q ≤ 200↵
This makes O(n²) solutions feasible.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
**Brute Force Solution**↵
↵
<spoiler summary="Solution 1">↵
For each element, follow the permutation until it loops back to the original position↵
</spoiler>↵
↵
↵
<spoiler summary="Code 1">↵
```python3↵
def check(p, n):↵
res = [0] * n↵
for i in range(n):↵
cnt = 1↵
cur = p[i] - 1↵
while cur != i:↵
cur = p[cur] - 1↵
cnt += 1↵
res[i] = cnt↵
return res↵
↵
q = int(input())↵
for _ in range(q):↵
n = int(input())↵
p = list(map(int, input().split()))↵
print(*check(p, n))↵
↵
```↵
</spoiler>↵
↵
<spoiler summary="Solution 2">↵
For each element, follow the permutation until it loops back to the original position↵
</spoiler>↵
↵
↵
<spoiler summary="Code 2">↵
↵
```python3↵
↵
from collections import defaultdict, deque↵
↵
q = int(input())↵
for _ in range(q):↵
n = int(input())↵
p = list(map(int, input().split()))↵
graph = defaultdict(list)↵
for i in range(1, n + 1):↵
graph[i].append(p[i - 1])↵
↵
ans = []↵
for i in range(1, n + 1):↵
queue = deque([i])↵
visited = {i}↵
days = 0↵
while queue:↵
node = queue.popleft()↵
for neighbour in graph[node]:↵
if neighbour not in visited and neighbour != node:↵
visited.add(neighbour)↵
queue.append(neighbour)↵
days += 1↵
ans.append(days + 1)↵
print(*ans)↵
↵
↵
```↵
</spoiler>↵
↵
**Optimal Solution**↵
↵
<spoiler summary = "Hint">↵
Can we see that every element belonging to the same cycle actually forms a group together?↵
↵
<spoiler summary="answer">↵
Yes, exactly! Each cycle in the permutation represents a group of elements that are all connected through mappings. So we can use Disjoint Set Union (DSU) to group these elements together. Once grouped, we can easily determine the size of each cycle by checking the size of each group.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution">↵
To solve the problem efficiently, we can use the **Disjoint Set Union (DSU)** data structure, also known as **Union-Find**, which is ideal for managing groups of connected elements. The core idea is to treat each cycle in the permutation as a group and then track these groups as we process the permutation.↵
↵
The DSU allows us to efficiently group elements together and later find the size of each group. For this problem, we will use **path compression** in the `find` operation to speed up future queries, and **union by size** to ensure we merge smaller groups into larger ones, which optimizes the union operation.↵
↵
We start by initializing the DSU for each test case, where each element is its own parent. Then, for each element in the permutation, we union the element with the one it points to. After processing all elements, we can use the `find` operation to determine the root of each element's cycle and then count the size of each cycle by checking the size of the connected group it belongs to.↵
↵
This approach ensures that we can efficiently handle the problem even with large inputs, as the time complexity for both union and find operations is nearly constant, due to the inverse Ackermann function, which grows extremely slowly. Thus, the solution is both time-efficient and space-efficient for large values of `n`.↵
↵
Time Complexity:↵
O(n * α(n)) per test case, where n is the number of elements and α(n) is the inverse Ackermann function. For practical input sizes, α(n) is very small, often treated as a constant.↵
↵
Space Complexity:↵
O(n) for storing the parent, rank (or size), and other DSU-related arrays.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
```python3↵
import sys↵
↵
input = sys.stdin.readline↵
↵
# Input helpers↵
I = lambda: int(input())↵
ILT = lambda: list(map(int, input().split()))↵
↵
class DSU:↵
def __init__(self, n):↵
self.rank = [0] * (n + 1)↵
self.parent = list(range(n + 1))↵
self.size = [1] * (n + 1)↵
↵
def find(self, node):↵
if node == self.parent[node]:↵
return node↵
stack = []↵
while node != self.parent[node]:↵
stack.append(node)↵
node = self.parent[node]↵
for n in stack:↵
self.parent[n] = node↵
return node↵
↵
def Sunion(self, u, v): # Union by size↵
rep_u = self.find(u)↵
rep_v = self.find(v)↵
if rep_u == rep_v:↵
return↵
if self.size[rep_u] < self.size[rep_v]:↵
self.parent[rep_u] = rep_v↵
self.size[rep_v] += self.size[rep_u]↵
else:↵
self.parent[rep_v] = rep_u↵
self.size[rep_u] += self.size[rep_v]↵
↵
def Runion(self, u, v): # Union by rank↵
rep_u = self.find(u)↵
rep_v = self.find(v)↵
if rep_u == rep_v:↵
return↵
if self.rank[rep_u] < self.rank[rep_v]:↵
self.parent[rep_u] = rep_v↵
elif self.rank[rep_v] < self.rank[rep_u]:↵
self.parent[rep_v] = rep_u↵
else:↵
self.parent[rep_v] = rep_u↵
self.rank[rep_u] += 1↵
↵
def solve():↵
n = int(input())↵
p = list(map(int , input().split()))↵
uf = DSU(n)↵
for i in range(n):↵
uf.Sunion(p[i], i + 1)↵
print(*[uf.size[uf.find(i)] for i in range(1, n + 1)])↵
↵
for _ in range(int(input())):↵
solve()↵
↵
```↵
</spoiler>↵
↵
↵
↵
#### [C. Destroy](https://mirror.codeforces.com/gym/608931/problem/C)↵
↵
<spoiler summary="Hint 1">↵
Instead of simulating destruction from the beginning, try **reversing** the process.↵
Imagine you start with an **empty array**, and at each step you **restore** one element.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
When you restore an element, you want to **join it with its neighbors** (if they are already restored), to form a **continuous segment**.↵
To track segments and their sums efficiently, you can use a structure that merges and finds connected components.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Use a **disjoint set** (also called union-find) to keep track of connected segments and their total sums.↵
Each restored position is its own segment initially. Then, if neighboring positions are restored, you merge them and update the total.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Here's the idea:↵
↵
- Process the array in **reverse destruction order** (i.e., imagine "restoring" the numbers).↵
- Keep track of which positions are active using a union-find structure.↵
- For each newly added number:↵
- Set its value.↵
- If neighbors are already restored, merge the segments.↵
- Update the **maximum segment sum** seen so far.↵
- Store the maximum sum after each restoration. At the end, reverse the answer to match the original destruction order.↵
↵
This approach works in **O(n * α(n))** where α is the inverse Ackermann function — effectively constant.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python↵
import sys↵
↵
# Union-Find (Disjoint Set Union) with segment sum tracking↵
class Dsu:↵
def __init__(self, size):↵
self.parent = [i for i in range(size + 1)] # parent[i] = leader of the set containing i↵
self.size = [1 for i in range(size + 1)] # size[i] = size of set with leader i↵
self.total = [-1 for i in range(size + 1)] # total[i] = sum of the segment with leader i↵
↵
def find(self, x):↵
# Path compression to find leader↵
if x != self.parent[x]:↵
self.parent[x] = self.find(self.parent[x])↵
return self.parent[x]↵
↵
def union(self, x, y):↵
# Merge two segments↵
px = self.find(x)↵
py = self.find(y)↵
↵
if px != py:↵
# Union by size (smaller into larger)↵
if self.size[px] > self.size[py]:↵
px, py = py, px↵
self.parent[px] = py↵
self.size[py] += self.size[px]↵
self.total[py] += self.total[px] # Update total segment sum↵
↵
↵
def solve():↵
n = int(sys.stdin.readline().strip())↵
nums = [0] + list(map(int, sys.stdin.readline().strip().split())) # 1-indexed↵
queries = list(map(int, sys.stdin.readline().strip().split())) # destruction order↵
↵
dsu = Dsu(n)↵
ans = [0] # answer after 0 restorations↵
maxi = 0 # current maximum segment sum↵
↵
# Process in reverse: simulate "restoring" elements↵
for val in queries[::-1]:↵
dsu.total[val] = nums[val] # restore the value at position `val`↵
↵
# Try to join with the left neighbor↵
if val - 1 > 0 and dsu.total[val - 1] > -1:↵
dsu.union(val - 1, val)↵
↵
# Try to join with the right neighbor↵
if val + 1 <= n and dsu.total[val + 1] > -1:↵
dsu.union(val + 1, val)↵
↵
# Get the sum of the segment that includes this restored value↵
cursum = dsu.total[dsu.find(val)]↵
maxi = max(maxi, cursum)↵
ans.append(maxi) # save current max after this restoration↵
↵
# Remove the last dummy value and reverse to match destruction order↵
ans.pop()↵
for val in ans[::-1]:↵
print(val)↵
↵
```↵
</spoiler>↵
↵
↵
#### [D. Masha and The Bear](https://mirror.codeforces.com/gym/608931/problem/D)↵
↵
<spoiler summary = "Solution 1">↵
<p>↵
Let’s use graph to represent the facts given in the problem. A node in the graph represents a snack flavour. Every guest likes exactly two different snack flavours, so an edge can be used to represent a guest by connecting two nodes(snack flavours) that the guest likes.↵
</p>↵
↵
<p>↵
For each connected component element, the first person will always eat two snacks. Then we can find an order in which every other person eats one until all the snacks are eaten. So the number of happy guests is ,<b>N — 1</b> where <b>N</b> is the number of nodes in that connected component. It’s guaranteed that such a sequence of guests always exist and there is no better way to make more guests happier. ↵
</p>↵
↵
<p>↵
So, a simple <b>dfs/bfs</b> can be used to find the answer. We can find the total number of happy guests by traversing each connected component separately. Then the number of unhappy guest will be the total number of guests minus the total number of happy guests.↵
</p>↵
↵
<p><b>Time and space complexities</b></p>↵
<ul>↵
<li>↵
<b> Time Complexity: O(n)</b>↵
</li>↵
<li>↵
<b> Space Complexity: O(n)</b>↵
</li>↵
</ul>↵
</spoiler>↵
↵
↵
<spoiler summary="Code 1">↵
```↵
from collections import defaultdict, deque↵
↵
n, k = map(int, input().split())↵
graph = defaultdict(list)↵
for _ in range(k):↵
l, r = map(int, input().split())↵
graph[l].append(r)↵
graph[r].append(l)↵
↵
def bfs(start):↵
q = deque([start])↵
visited.add(start)↵
↵
count = 0↵
while q:↵
node = q.popleft()↵
count += 1↵
↵
for child in graph[node]:↵
if child not in visited:↵
q.append(child)↵
visited.add(child)↵
↵
return count↵
↵
↵
happy = 0↵
visited = set()↵
for i in range(1, n + 1):↵
if i not in visited:↵
happy += bfs(i) - 1↵
↵
print(k - happy)↵
↵
↵
```↵
</spoiler>↵
↵
↵
<spoiler summary = "Solution 2">↵
↵
The problem can be reduced to finding the number of edges that form cycles in a graph where nodes are snacks and edges are guests (connecting their two favorite flavors). In a tree (a connected component without cycles), we can always order guests so that no one is sad each guest arrives when at least one favorite snack is still available. However, cycles force at least one sad guest because, no matter the order, some guest will find both snacks already eaten. For this we can use DSU.↵
↵
Each time we try to connect two already linked nodes, it means we’ve found a cycle, and thus a sad guest. The total number of such edges gives the minimum sad guests, as trees contribute zero and each cycle adds exactly one unavoidable sad guest.↵
↵
<p><b>Time and space complexities</b></p>↵
<ul>↵
<li>↵
<b> Time Complexity: O(k)</b>↵
</li>↵
<li>↵
<b> Space Complexity: O(k)</b>↵
</li>↵
</ul>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code 2">↵
```↵
class UnionFind:↵
def __init__(self, size):↵
self.parent = {i:i for i in range(size)}↵
self.sizes = {i:1 for i in range(size)}↵
↵
def find(self, x):↵
while x != self.parent[x]:↵
self.parent[x] = self.parent[self.parent[x]]↵
x = self.parent[x]↵
return x↵
↵
def union(self, x, y):↵
root1 = self.find(x)↵
root2 = self.find(y)↵
↵
if root1 == root2:↵
return False↵
↵
if self.sizes[root2] > self.sizes[root1]:↵
root1,root2 = root2,root1↵
↵
self.parent[root2] = root1↵
self.sizes[root1] += self.sizes[root2]↵
↵
return True↵
↵
↵
n, k = map(int, input().split())↵
↵
answer = 0↵
↵
dsu = UnionFind(n + 1) ↵
↵
for _ in range(k):↵
u, v = map(int, input().split())↵
↵
if not dsu.union(u, v):↵
answer += 1↵
↵
↵
print(answer)↵
↵
```↵
</spoiler>↵
↵
↵
#### [E. Wide, Wide Graph](https://mirror.codeforces.com/gym/608931/problem/E)↵
↵
<spoiler summary = "Hint"> What if we think in reverse: from a graph with no edges to adding edges based on distance? </spoiler>↵
↵
↵
<spoiler summary = "Solution"> ↵
We are given a tree, and for each integer $k$ from 1 to $n$, we must count the number of connected components in a graph $Gk$, where an edge exists between two nodes only if their distance in the tree is at least $k$.↵
Instead of checking all pairs of nodes for each $k$, which would be too slow $O(n^2)$, we take advantage of tree properties:↵
↵
- In a tree, there's a unique path between any two nodes. So we can define the "distance" easily using BFS or DFS.↵
↵
- Let’s fix a special node the farthest node from any random node (say, node $0$). From that, perform BFS to find ↵
the node furthest from it this gives one endpoint of the diameter. Do a final BFS from this endpoint to get the actual diameter and each node’s distance from it. We then compute the maximum distance for each node from either endpoint of the diameter. If the maximum distance of a node is less than $k$, then this node becomes isolated in $Gk$ since no other node is at distance ≥ $k$. ↵
↵
Hence, for each $k$, we count how many nodes become isolated (i.e., their max distance $k$, and increment the number of components accordingly.↵
This gives an $O(n)$ solution using just a few BFS traversals and basic counting.↵
↵
</spoiler>↵
↵
<spoiler summary="Code">↵
```python3↵
from collections import deque↵
↵
def bfs(tree, start):↵
n = len(tree)↵
dist = [-1] * n↵
dist[start] = 0↵
q = deque([start])↵
while q:↵
node = q.popleft()↵
for neighbor in tree[node]:↵
if dist[neighbor] == -1:↵
dist[neighbor] = dist[node] + 1↵
q.append(neighbor)↵
return dist↵
↵
def main():↵
n = int(input())↵
↵
tree = [[] for _ in range(n)]↵
for _ in range(n - 1):↵
u, v = map(int, input().split())↵
# Convert to 0-based index ↵
u -= 1↵
v -= 1↵
tree[u].append(v)↵
tree[v].append(u)↵
↵
# Step 1: BFS from arbitrary node (0) to find one endpoint of diameter↵
d1 = bfs(tree, 0)↵
far1 = d1.index(max(d1))↵
↵
# Step 2: BFS from far1 to get distances and find farthest point (diameter)↵
d2 = bfs(tree, far1)↵
diameter = max(d2)↵
far2 = d2.index(diameter)↵
↵
# Step 3: BFS from far2 to get second set of distances↵
d3 = bfs(tree, far2)↵
↵
# For each node, take the maximum distance to either end of diameter↵
max_dist = [max(d2[i], d3[i]) for i in range(n)]↵
↵
# Count how many nodes have max_dist < k↵
isolated_count = [0] * (n + 2)↵
for d in max_dist:↵
isolated_count[d] += 1↵
↵
result = [1] # G_1 has 1 component (the whole tree)↵
for k in range(2, n + 1):↵
if k > diameter:↵
result.append(n)↵
else:↵
result.append(result[-1] + isolated_count[k - 1]) ↵
↵
print(' '.join(map(str, result)))↵
↵
main()↵
↵
```↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
