LongestPathInTree

using System;
using System.Collections.Generic;
using System.Linq;

namespace _4.Longest_Path_in_a_Tree
{
    class LongestPathInTree
    {
        static void Main()
        {
            int n = int.Parse(Console.ReadLine());
            int m = int.Parse(Console.ReadLine());
            Dictionary<int, List<int>> parentChildrens =
                new Dictionary<int, List<int>>();
            Dictionary<int, int?> parents =
                new Dictionary<int, int?>();

            for (int i = 0; i < m; i++)
            {
                var nums = Console.ReadLine().Split(' ')
                    .Select(int.Parse)
                    .ToList();
                int first = nums[0];
                int second = nums[1];

                if (!parentChildrens.ContainsKey(first))
                {
                    parentChildrens[first] = new List<int>();
                }

                if (!parentChildrens.ContainsKey(second))
                {
                    parentChildrens[second] = new List<int>();
                }

                if (!parents.ContainsKey(second))
                {
                    parents[second] = first;
                }

                if (!parents.ContainsKey(first))
                {
                    parents[first] = null;
                }

                parentChildrens[first].Add(second);
                parents[second] = first;
            }

            var leaves = parentChildrens
                .Where(p => p.Value.Count == 0)
                .Select(p => p.Key)
                .ToList();

            var root = parents
                .First(p => p.Value == null)
                .Key;
            var pathsToRootList = new List<List<int>>();

            foreach (var leaf in leaves)
            {
                int currNode = leaf;
                List<int> currentPath = new List<int>();
                while (currNode != root)
                {
                    currentPath.Add(currNode);
                    currNode = (int)parents[currNode];
                }
                pathsToRootList.Add(currentPath);
            }

            int maxSum = 0;

            for (int i = 0; i < pathsToRootList.Count; i++)
            {
                maxSum = pathsToRootList.Where((t, j) => i != j &&
                    !pathsToRootList[i].Intersect(t).Any())
                    .Select(t => pathsToRootList[i].Sum() + t.Sum() + root)
                    .Concat(new[] {maxSum})
                    .Max();
            }

            Console.WriteLine();
            Console.WriteLine(maxSum);
        }
    }
}