We are given a graph. Initially graph is empty.↵
There are three type of operation we can perform on graph.↵
↵
1. _insertType1_ value↵
2. _insertType2_ value parentNodeId↵
3. _query_ nodeId maxDistance ↵
↵
↵
Both _insertType1_ and _insertType2_ adds node to the graph. ↵
Newly added node will have new _NodeId_ which will be auto incremented (starting from 0).↵
↵
↵
~~~~~↵
For example, ↵
first node inserted will have nodeId = 0↵
second node inserted will have nodeId = 1↵
third node inserted will have nodeId = 2↵
and so on.↵
~~~~~↵
↵
↵
↵
_insertType2_ takes parent node id as second argument.↵
So there will be directed edge from parent node to newly generated node.↵
↵
↵
These insert operations will form graph which contains multiple directed tree graph.↵
↵
↵
_insertType1_ and _insertType2_ operator should print nodeId.↵
_query_ operator should print sum of values of all nodes which are descendent of node with id equals to _nodeId_ and descendents should not be far more than _maxDistance_.↵
↵
↵
Sample Input:↵
↵
↵
~~~~~↵
insertType1 11↵
insertType2 12 0↵
insertType2 13 0↵
query 0 0↵
query 0 1↵
insertType2 14 1↵
insertType2 15 2↵
insertType2 16 3↵
insertType2 17 3↵
insertType2 18 3↵
query 3 1↵
query 0 2↵
query 1 1↵
~~~~~↵
↵
↵
↵
Sample Output:↵
↵
~~~~~↵
0↵
1↵
2↵
11↵
36↵
3↵
4↵
5↵
6↵
7↵
65↵
65↵
26↵
~~~~~↵
↵
↵
↵
↵
example tree:↵
↵
11 ↵
/ \↵
12 13↵
/ \↵
14 15↵
/ | \ ↵
16 17 18↵
↵
↵
Brute for approach for query operation will require breadth first search for every query.↵
↵
Any Idea how to answer queries efficiently? Looking for an online algorithm.
There are three type of operation we can perform on graph.↵
↵
1. _insertType1_ value↵
2. _insertType2_ value parentNodeId↵
3. _query_ nodeId maxDistance ↵
↵
↵
Both _insertType1_ and _insertType2_ adds node to the graph. ↵
Newly added node will have new _NodeId_ which will be auto incremented (starting from 0).↵
↵
↵
~~~~~↵
For example, ↵
first node inserted will have nodeId = 0↵
second node inserted will have nodeId = 1↵
third node inserted will have nodeId = 2↵
and so on.↵
~~~~~↵
↵
↵
↵
_insertType2_ takes parent node id as second argument.↵
So there will be directed edge from parent node to newly generated node.↵
↵
↵
These insert operations will form graph which contains multiple directed tree graph.↵
↵
↵
_insertType1_ and _insertType2_ operator should print nodeId.↵
_query_ operator should print sum of values of all nodes which are descendent of node with id equals to _nodeId_ and descendents should not be far more than _maxDistance_.↵
↵
↵
Sample Input:↵
↵
↵
~~~~~↵
insertType1 11↵
insertType2 12 0↵
insertType2 13 0↵
query 0 0↵
query 0 1↵
insertType2 14 1↵
insertType2 15 2↵
insertType2 16 3↵
insertType2 17 3↵
insertType2 18 3↵
query 3 1↵
query 0 2↵
query 1 1↵
~~~~~↵
↵
↵
↵
Sample Output:↵
↵
~~~~~↵
0↵
1↵
2↵
11↵
36↵
3↵
4↵
5↵
6↵
7↵
65↵
65↵
26↵
~~~~~↵
↵
↵
↵
↵
example tree:↵
↵
11 ↵
/ \↵
12 13↵
/ \↵
14 15↵
/ | \ ↵
16 17 18↵
↵
↵
Brute for approach for query operation will require breadth first search for every query.↵
↵
Any Idea how to answer queries efficiently? Looking for an online algorithm.
