Detecting Intrusions in a Network

5

3 votes
Trees, Lowest Common Ancestor, Data Structures
Problem

Imagine you are responsible for the security of a complex computer network comprising multiple interconnected devices. Each device is represented as a node in a tree-like structure, with connections between them forming the network. Your task is to assess potential security threats within this network.

The network has N nodes and node 1 is designated as the root device.

You are given a series of queries, with each query consisting of the following:

  1. Two device IDs (nodes) representing a pair of devices within the network.
  2.  A threshold value K representing the acceptable security risk level.

Your goal is to determine the security status between these two devices by calculating the XOR of all the intermediate nodes (devices) in the path connecting them. Here's how to assess the security status:

If the XOR value between the two nodes exceeds the threshold K, you must respond with: ALERT. This indicates that the security risk between these devices is considered high, and immediate action may be required to investigate potential intrusions.
If the XOR value is less than or equal to K, your response should be: SECURE.This suggests that the security risk is within an acceptable range and the connection between the two devices is considered relatively secure.

Your solution aims to efficiently process these queries, allowing for dynamic security assessments based on different threshold values K and providing actionable insights to maintain the network's security.

Input Format:

  • The first line contains an integer N, representing the number of nodes in the network. 
  • The following N1 lines, each contain two space-separated integers U and V representing the connection between nodes U and V.
  • The next line contains an integer Q, representing the number of queries.
  • The following Q lines, each contain three space-separated integers U,V and K, where U and V are the device IDs (nodes) for a pair of devices, and K is the threshold value for assessing the security status.

Output Format:

Output Q lines with each line stating that whether the network is in ALERT condition or SECURE condition.

Constraints:

  • 1N21e5: Number of nodes in the network
  • 1Q21e5: Number of queries
  • 1U,VN: Representing device IDs (nodes) for a pair of devices
  • 1K1e9: Threshold value for intrusion detection
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

  • For query 1 : XOR between 2 and 5 is 5 (2^1^3^5) which is less than the threshold 10 that's why system is in SECURE condition.
  • For query 2:  XOR between 6 and 7 is 5 (6^4^7) which is greater than the threshold 3 that's why system is in ALERT condition.
  • For query 3 XOR between 1 and 4 is 6 (1^3^4) which is greater than the threshold 1 that's why system is in ALERT condition.
Editor Image

?