CareerCup

The way nodes are added makes it into a tree.
Consider the first node as a root. Every new node is a leaf.

Lets have a node to have following structure:

class Node{
	Node parent; // so we can walk up 

	int maxDistanceToLeaf = 0;
	int secondToMaxDistanceToLeaf = 0;
	
	//These two nodes MUST be different
	//They are two immediate children to this node from which the two max paths came
	Node childForMaxDistanceToLeaf;
	Node childForSecondToMaxDistanceToLeaf;
}

On every node addition, walk up a tree all the way to the root and on every node on the way update two max distances to leaf if any of them needs to be updated, as well as 2 associated children nodes.
Note maximum maxDistanceToLeaf+secondToMaxDistanceToLeaf. If it is larger than previous diameter, this will be new diameter. otherwise, new diameter does not change.

Time complexity: In case nodes are added to random nodes n log n. If not making such assumption: n*diameter. Because in average, path from leaf to root is equal or less half of diameter.

Memory complexity is just n

/*

Observation 1 : It will always be a tree
Observation 2: if u-v is the diameter after adding x node diameter will be u-v,u-x or v-x one of these 3.

we can find diameter using LCA although my solution can be improved but its given an idea
total complexity is around n*(depth) or nlogn

*/


#include <iostream>
#include <vector>
using namespace std;

#define MAX 100000
vector<int> parent(MAX,-1);

int find(int x)
{
int ans=0;
while(parent[x]!=x)
{
x=parent[x];
ans++;
}

return ans;
}

int diameter(int x, int y)
{
int hx = find(x);
int hy = find(y);
int lca = 0;
int ofset = hx-hy;
int d=ofset;

if(d<0)
d=-d;
if(ofset>0)
{
while(ofset--)
x=parent[x];

}

else
{
ofset=-ofset;
while(ofset--)
y=parent[y];
}

while(1)
{
if(x==y) break;
x=parent[x];
y=parent[y];
lca++;
}

return 2*lca + d;


}
int main()
{

parent[0]=0;

int n; cin>>n;
int size=1;
int d1,d2,dist=0;

for(int i=1;i<=n;i++)
{
int p,c;
cin>>p;
c=i;
// c is child of p
parent[c]=p;
size++;

if(size==2)
{
d1 = 0;
d2 = 1;
dist = 1;
cout<<1<<endl;
continue;
}

// after that answer will be d1--d2 or d1---c or d2--c

int dist1 = diameter(d1,c);
int dist2 = diameter(d2,c);


if(dist1>dist) { dist=dist1; d2=c; }
else if (dist2>dist) { dist=dist2; d1=c;}


cout<<dist<<endl;





}

//for(int i=0;i<=n;i++)
//cout<<i<<" "<<find(i)<<endl;


}

We keep a (symmetric) matrix of distances. More precisely, x(i, j) is the distance between nodes i and j.

When we add node k to node i, we set, for all j < k, x(k, j) = x(j, k) = x(i, j) + 1, that is, the distance from node k (the new one) to node j is one more than the distance from j to i (the node which k is connected to).

#include <vector>
#include <iostream>

class graph {

    unsigned N_;
    std::vector<unsigned> x_; // storage for x

    unsigned n_ = 1, d_ = 0;

    unsigned& x(int i, int j) { return x_[i * N_ + j]; }

public:

    graph(unsigned N) : N_(N + 1), x_(N_ * N_) { }

    unsigned insert(unsigned n) {
        for (unsigned j = 0; j < n_; ++j) {
            unsigned y = x(n, j) + 1;
            x(n_, j) = y;
            x(j, n_) = y;
            d_ = y > d_ ? y : d_;
        }
        ++n_;
        return d_;
    }
};

int main() {
    unsigned N;
    std::cin >> N;
    graph g(N);
    for (unsigned i = 0; i < N; ++i) {
        int n;
        std::cin >> n;
        std::cout << g.insert(n) << '\n';
    }
}

**Edit:** This is not asymptotically optimal. See CT's answer...

[WRONG: I think this is asymptotically optimal:]

// TIME:    O(N) for update on every node insertion; O(N^2) total
// MEMORY:  O(N^2) for storing all pair-wise distances
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1010;

/*
 * sz     -> nodes in the graph
 * max_di -> current diameter
 * di     -> pair-wise distance between nodes
 * wh     -> wh[i] is index of node that is farthest from node i
 */
struct Graph {
  int sz;
  int max_di;
  int di[MAXN][MAXN];
  int wh[MAXN];
  
  Graph(): sz(1), max_di(0), di{0}, wh{0} {}
  int insert(int);
  void write_di(int x, int y, int d) { di[x][y] = di[y][x] = d; };
};

int Graph::insert(int n) {
  wh[sz] = 0;
  for (int i = 0; i < sz; ++i) {
    // pair-wise distance between new node and every node already in graph
    write_di(sz, i, di[i][n] + 1);
    // new distances contend for maximal distance
    max_di = max(max_di, di[sz][i]);

    // update farthest node for new node
    if (di[sz][wh[sz]] < di[sz][i]) {
      wh[sz] = i;
    }

    // update farthest node for every node already in graph
    if (di[i][wh[i]] < di[i][sz]) {
      wh[i] = sz;
    }
  }
  ++sz;

  return max_di;
}

int main() {
  Graph graph;
  int N;
  cin >> N;
  for (int i = 0; i < N; ++i) {
    int tmp;
    cin >> tmp;
    cout << graph.insert(tmp) << endl;
  }
}

1. Keep a int distanceFromNode for all Nodes indicating it's distance from Root.
2. Keep track of the of longest and 2nd longest. 1st and 2nd Longest must be in 2 different branches starting from root. One way to check this is keeping track of the 1st and 2nd longest paths using 2 Lists or HashSets.
3. Sum of Longest and second Longest will give you the current tree diameter.
4. While adding nodes to the tree, calculate it's distance from root getting Parent distance + 1
5. If node added has distance > longest or distance > 2nd longest - Node added is 1st or 2nd new longest, update diameter. Update 1st and 2nd Max paths node sets.

I am thinking, based on the assumption that
1. The graph is a tree
2. The shortest distance between any node pair will not change after a new node is added,

then we can use a DP like solution.
When a node is added, the distance between the new node and the node it connects is 1. Then we calculate the shortest distance between the new node and all previous node based on the connection between existing nodes.

Please let me know if my assumption is wrong.

public class Diameter {
	static int N;
	static int[][] shortestPath;
	static int newNode = 0;
	public static void maxShortestDistance(String input){
		Stdin inStream = new Stdin(input);
		N = Integer.parseInt(inStream.readLine());
		shortestPath = new int[N + 1][N + 1];
		for(int i = 0; i <= N; i++)
			//Integer.MAX_VALUE will overflow
			Arrays.fill(shortestPath[i], Integer.MAX_VALUE / 2);
		for(int i = 0; i <= N; i++)
			shortestPath[i][i] = 0;
		int max = 0;
		try{
			while(!inStream.isEmpty()){
				newNode++;
				int connected = Integer.parseInt(inStream.readLine());
				shortestPath[connected][newNode] = 1;
				shortestPath[newNode][connected] = 1;
				for(int i = 0; i < newNode; i++){
					for(int j = 0; j < newNode; j++){
						shortestPath[i][newNode] = Math.min(shortestPath[i][newNode], 
								shortestPath[i][j] + shortestPath[j][newNode]);
					}
					shortestPath[newNode][i] = shortestPath[i][newNode];
					max = Math.max(max, shortestPath[i][newNode]);
					//System.out.println(i + " to " + newNode + ": " + shortestPath[newNode][i]);
				}
				System.out.println(max);
			}
		} catch (Exception e){
			System.out.println(e);
		}
		
		inStream.close();
	}

	public static void main(String[] args) {
		maxShortestDistance("maxShortestDistance.txt");
	}
}

Python version.

import sys
class graph:
    def __init__(self, n):
        self.n = n
        self.diameter = 0
        self.root_children = []
        self.child_parent = {}
        self.node_depth = {}
        self.node_depth[0] = 0

    def update_depth(self, node, val):
        if self.node_depth[node] < val:
            self.node_depth[node] = val
            if node != 0:
                self.update_depth(self.child_parent[node], val+1)

    def add_node(self, c, p):
        self.child_parent[c] = p
        if p == 0:
            self.root_children.append(c)
        self.node_depth[c] = 0
        self.update_depth(p, 1)

        if len(self.root_children) == 1:
            self.diameter = self.node_depth[0]
        else:
            a = -1
            b = -2
            for i in range(0, len(self.root_children)):
                x = self.node_depth[self.root_children[i]]
                if x > a:
                    b = a
                    a = x
                elif x > b:
                    b = x
            self.diameter = a+b+2

#main
n = 0
g = None
for i, line in enumerate(sys.stdin):
    if i == 0:
        n = int(line)
        g = graph(n)
    elif i > n:
        break 
    else:
        g.add_node(i, int(line))
        print g.diameter





print "\n\ngraph:"
print g.n, g.diameter, g.root_children, g.child_parent, g.node_depth

Here is my solution.

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;

public class Tree {
	
 int distance[][];
 Node root;
 int numVertices;
 
 class Node {
	 int value;
	 ArrayList<Node> children = new ArrayList<Node>();
	 Node(int id) {
		 value = id;
	 }	 
 }
 
 Node findNodeInTree(int parentId,Node root) {
	if(root == null)
		return null;
	if(root.value == parentId)
		return root;
	for(Node n:root.children) {
		Node res = findNodeInTree(parentId,n);
		if(res!=null)
			return res;
	}
	return null;
 }
 
 void addNode(int id, int parentId) {
	 Node node = new Node(id);	
	 if(root == null) {
		 root = node;		 
	 } else {
		 Node parent = findNodeInTree(parentId,root);
		 parent.children.add(node);		 
		 distance[parentId][id] = 1;
		 for (int i = 0; i < id; i++) {			 
				 distance[id][i] = 1 + distance[parentId][i];
				 if(distance[i][id] < distance[id][i])
					 distance[i][id] = distance[id][i];
		 }
		 if(parent.children.size() <= 2) {
			 updateDiameter();
		 }
		 System.out.println(diameter);
	 }
 }
 
 int diameter = 0;
 
 private void updateDiameter() {
	 for (int i = 0; i < numVertices; i++) {
		 for (int j = 0; j < numVertices; j++) {
		  diameter = Math.max(diameter, distance[i][j]);
	 }
 }
}
 int id = 1;
 void readTree(String fileName) {
	
	 try {
		BufferedReader br = new BufferedReader(new FileReader(fileName));
		
		try {
			String line = br.readLine();
			numVertices = Integer.parseInt(line);
			numVertices++;
			distance = new int[numVertices][numVertices];			
			addNode(0, 0);
						
			while((line = br.readLine())!=null) {
				int parentId = Integer.parseInt(line);
				addNode(id, parentId);
				id++;
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	} catch (FileNotFoundException e) {
		// TODO Auto-generated catch block
		e.printStackTrace();
	}
 }
}

I think its really simple question, I am not sure why all the other answers are all complex.

you just need to keep track of the diameter of the node you are attaching to, and 1 to it.

return the maximum diameter for each new node.

def calcDiameter(numOfNodes, nodes):
    if nodes == None or nodes == []:
        return []
    maximum = 1
    vals = [1]
    diameters = [1]

    for node in nodes[1:]:
        newVal = vals[node]+1
        if newVal > maximum:
            maximum = newVal
        vals.append(newVal)
        diameters.append(maximum)
    return diameters

print calcDiameter(5, [0,0,1,1,1])

Sure this graph is actually a tree, but each node only has a reference to its parent. In this case, we would not be able to access the 'roots' subtrees. My solution works around this by using the property of the diameter only growing when connecting a new node to a parent that has less than 2 connections:

This is my first submission, please be nice lol :X

import java.util.HashMap;


public class Diameter {
	
	public static void main(String[] args) {
		Diameter d = new Diameter();
		System.out.println(d.addNode(0, 1));
		System.out.println(d.addNode(0, 2));
		System.out.println(d.addNode(1, 3));
		System.out.println(d.addNode(1, 4));
		System.out.println(d.addNode(1, 5));
	}
	
	private HashMap<Integer,Node> map;
	private HashMap<Integer,Integer> connections;
	private int diameter;
	
	public Diameter(){
		diameter=0;
		map = new HashMap<Integer,Node>();
		connections = new HashMap<Integer,Integer>();
		Node n = new Node(0);
		map.put(0, n);
		connections.put(0, 0);
	}
	
	public int addNode(int par, int i){
		Node n = new Node(i, par);
		if (connections.get(par)<2)
			diameter++;
		connections.put(par, connections.get(par)+1);
		map.put(i,n);
		connections.put(i, 1);
		return diameter;
	}
	
	public class Node{
		int id;
		Node parent;
		public Node(int i){
			id=i;
			parent=null;
		}
		public Node(int i, int p){
			id=i;
			parent = map.get(p);
		}
	}
}

Sure this graph is actually a tree, but each node only has a reference to its parent. In this case, we would not be able to access the 'roots' subtrees. My solution works around this by using the property of the diameter only growing when connecting a new node to a parent that has less than 2 connections:

This is my first submission, please be nice lol :X

import java.util.HashMap;


public class Diameter {
	
	public static void main(String[] args) {
		Diameter d = new Diameter();
		System.out.println(d.addNode(0, 1));
		System.out.println(d.addNode(0, 2));
		System.out.println(d.addNode(1, 3));
		System.out.println(d.addNode(1, 4));
		System.out.println(d.addNode(1, 5));
	}
	
	private HashMap<Integer,Node> map;
	private HashMap<Integer,Integer> connections;
	private int diameter;
	
	public Diameter(){
		diameter=0;
		map = new HashMap<Integer,Node>();
		connections = new HashMap<Integer,Integer>();
		Node n = new Node(0);
		map.put(0, n);
		connections.put(0, 0);
	}
	
	public int addNode(int par, int i){
		Node n = new Node(i, par);
		if (connections.get(par)<2)
			diameter++;
		connections.put(par, connections.get(par)+1);
		map.put(i,n);
		connections.put(i, 1);
		return diameter;
	}
	
	public class Node{
		int id;
		Node parent;
		public Node(int i){
			id=i;
			parent=null;
		}
		public Node(int i, int p){
			id=i;
			parent = map.get(p);
		}
	}
}

Two observations...

(1) The graph is always a tree, and the first node is always the root.
(2) The diameter only increases when the parent of the new node didn't already have any children.

The following solution in Python hopefully works. I've taken the shortcut here of just representing nodes as unique integers. The kind of surprising thing here is that we don't even need to remember the tree structure at all -- we just remember the degree of each vertex, where degree is the number of edges incident on the vertex (ingoing or outgoing).

class NodeConsumer:
    def __init__(self):
        # 0 is the root.
        self.degrees = {0: 0}
        self.diameter = 0

    def add_node(self, n, p):
        self.degrees[n] = 1
        if self.degrees[p] <= 1:
            self.diameter += 1
        self.degrees[p] += 1

    def get_diameter(self):
        return self.diameter