using System; using System.Collections.Generic; using System.Text; using System.Linq; class Program { public void Proc() { Reader.IsDebug = false; int muraCount = int.Parse(Reader.ReadLine()); this.MuraList = new TreeNode[muraCount]; for(int i=0; i> road = new Dictionary>(); for(int i=0; iint.Parse(a)).ToArray(); if(!road.ContainsKey(inpt[0])) { road.Add(inpt[0], new Dictionary()); } road[inpt[0]].Add(inpt[1], true); if(!road.ContainsKey(inpt[1])) { road.Add(inpt[1], new Dictionary()); } road[inpt[1]].Add(inpt[0], true); } for(int i=0; iint.Parse(a)).ToArray(); long tax = this.GetTax(inpt[0], inpt[1]); tax *= inpt[2]; ans += tax; } Console.WriteLine(ans); } private Dictionary> taxDic = new Dictionary>(); private int GetTax(int fromId, int toId) { if(!this.taxDic.ContainsKey(fromId)) { this.taxDic.Add(fromId, new Dictionary()); } if(!this.taxDic.ContainsKey(toId)) { this.taxDic.Add(toId, new Dictionary()); } if(this.taxDic[fromId].ContainsKey(toId)) { return this.taxDic[fromId][toId]; } int ans = 0; if(fromId == toId) { ans = this.MuraList[fromId].Tax; } else { TreeNode fromMura = this.MuraList[fromId]; TreeNode toMura = this.MuraList[toId]; if(fromMura.Depth > toMura.Depth) { ans = this.GetTax(fromMura.Parent.NodeId, toId) + fromMura.Tax; } else { ans = this.GetTax(fromId, toMura.Parent.NodeId) + toMura.Tax; } } this.taxDic[fromId].Add(toId, ans); if(fromId != toId) { this.taxDic[toId].Add(fromId, ans); } return ans; } private void SetTree(int current, Dictionary> dic) { TreeNode node = this.MuraList[current]; dic[current].Keys.ToList().ForEach(a=>{ if(node.Parent == null || node.Parent.NodeId != a) { node.AddItem(this.MuraList[a]); } }); node.Items.ForEach(a=>SetTree(a.NodeId, dic)); } private TreeNode[] MuraList; public class TreeNode { public int NodeId = 0; public int Depth = 0; public TreeNode Parent; public List Items = new List(); public int Tax = 0; public TreeNode AddItem(TreeNode newChild) { newChild.Parent = this; this.Items.Add(newChild); newChild.Depth = this.Depth + 1; return newChild; } public TreeNode(int id) { this.NodeId = id; } } public class Reader { public static bool IsDebug = true; private static String PlainInput = @" 2 0 1 11 7 2 0 1 3 1 0 2 "; private static System.IO.StringReader Sr = null; public static string ReadLine() { if (IsDebug) { if (Sr == null) { Sr = new System.IO.StringReader(PlainInput.Trim()); } return Sr.ReadLine(); } else { return Console.ReadLine(); } } } static void Main() { Program prg = new Program(); prg.Proc(); } }