Submission #2554803

---

Source Code Expand

using System;
using System.Collections.Generic;
using System.Threading;

namespace Abc070d
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());

            List<List<int>> branches = new List<List<int>>();
            for (int i = 0; i < n - 1; i++)
            {
                string[] input = Console.ReadLine().Split(' ');
                List<int> branch = new List<int>()
                {
                    int.Parse(input[0]),
                    int.Parse(input[1]),
                    int.Parse(input[2])
                };
                branches.Add(branch);
            }

            string[] query = Console.ReadLine().Split(' ');
            int q_num = int.Parse(query[0]);
            int k = int.Parse(query[1]);

            long[] dp = new long[n + 1];
            dp[k] = 0;
            List<int> queue = new List<int>();
            queue.Add(k);
            List<int> yet = new List<int>();
            for (int i = 0; i < n - 1; i++)
            {
                yet.Add(i);
            }
            while (queue.Count > 0)
            {
                int current = queue[0];
                queue.RemoveAt(0);

                List<int> found = yet.FindAll(index => branches[index][0] == current || branches[index][1] == current);
                foreach (int index in found)
                {
                    List<int> branch = branches[index];
                    if (branch[0] == current)
                    {
                        dp[branch[1]] = dp[current] + branch[2];
                        queue.Add(branch[1]);
                        yet.Remove(index);
                        continue;
                    }

                    if (branch[1] == current)
                    {
                        dp[branch[0]] = dp[current] + branch[2];
                        queue.Add(branch[0]);
                        yet.Remove(index);
                    }
                }
            }

            for (int i = 0; i < q_num; i++)
            {
                string[] q = Console.ReadLine().Split(' ');
                int x = int.Parse(q[0]);
                int y = int.Parse(q[1]);

                Console.WriteLine(dp[x] + dp[y]);
            }
        }
    }
}

Submission Info

Judge Result