Honeypot
DESCRIPTION
Using credentials flagged in the previous investigation, Volnayan APTs have successfully breached a critical internal router. Telemetry from the affected systems indicates active lateral movement attempts.
As Orion “Circuitbreaker” Zhao, your mission is to contain the breach before it spreads further into critical infrastructure. You have a single opportunity to deploy a firewall between two network nodes to limit exposure. However, a honeypot node — strategically placed for surveillance — must remain reachable from the compromised root node.
The objective is to determine the minimum number of nodes that will still be reachable (i.e., exposed) from the root node after placing the firewall optimally, while ensuring the honeypot remains connected.
The input has the following format:
The first line contains an integer N.
The network is a tree with N nodes and N-1 connections.
The next N-1 lines describe the connections of the network, with a format of “A - B”, where A and B are integer IDs, representing network nodes.
The last line of the input defines the honeypot’s node ID, H (2 <= H <= N).
10 <= N <= 10^6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Example:
Input:
7
1 - 2
1 - 3
3 - 4
3 - 5
1 - 6
6 - 7
5
Expected output:
5
We can construct the following network tree with our input:
__ 1 ___
/ | \
2 3 6
/ \ \
4 5(H) 7
By placing the firewall between nodes 1 and 3, the nodes 3, 4, and 5 would be cut off from the network, leaving a total of 4 exposed nodes (1, 2, 6, 7).
That is the maximum number of nodes we can cut off with one firewall, but since node 5 is the honeypot and must be left exposed, the firewall cannot be placed between nodes 1 and 3.
Placing the firewall between nodes 1 and 6 which will cut off nodes 6 and 7 from the network.
This leaves us with 5 exposed nodes (1, 2, 3, 4, and 5), which is the minimum number, given the problem restriction of keeping the honeypot node exposed.
SOLUTION
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import sys
sys.setrecursionlimit(10**7)
def solve():
import sys
input = sys.stdin.read
data = input().splitlines()
N = int(data[0])
adj = [[] for _ in range(N + 1)]
for i in range(1, N):
a, b = map(int, data[i].split(' - '))
adj[a].append(b)
adj[b].append(a)
H = int(data[-1]) # Honeypot node
subtree_size = [0] * (N + 1)
parent = [0] * (N + 1)
on_path_to_honeypot = set()
# DFS to get subtree sizes and parents
def dfs(u, p):
subtree_size[u] = 1
parent[u] = p
for v in adj[u]:
if v != p:
dfs(v, u)
subtree_size[u] += subtree_size[v]
dfs(1, 0)
# Trace path from honeypot to root
cur = H
while cur != 0:
on_path_to_honeypot.add(cur)
cur = parent[cur]
max_hidden = 0
for u in range(2, N + 1): # skip root
if u not in on_path_to_honeypot:
max_hidden = max(max_hidden, subtree_size[u])
print(N - max_hidden)
solve()