using System; using System.Collections.Generic; using System.Linq; using System.IO; using static System.Console; using static System.Convert; using static System.Math; using System.Text; using Pi=csat.Pair; using PL=csat.Pair; namespace csat { class Program { public static bool chmin(ref T t,T v)where T:IComparable {if(t.CompareTo(v)==1){t=v;return true;} return false;} public static bool chmax(ref T t,T v)where T:IComparable {if(t.CompareTo(v)==-1){t=v;return true;}return false;} public static void swap(ref T t1,ref T t2) {var tm=t1;t1=t2;t2=tm;} public static void Fail(T s) {WriteLine(s);Console.Out.Close();Environment.Exit(0);} static void Main(string[] args) { var sw=new StreamWriter(Console.OpenStandardOutput()){AutoFlush=false}; Console.SetOut(sw); var p=new Program(); for(var i=1;i>0;i--) p.Solve(); Console.Out.Flush(); } void Solve(){ var num=Input.num; var tr=new Tree(num); for(var i=0;i0){ int x,y,z; Input.Make(out x,out y,out z); var res=long.MaxValue; var lca=tr.LCA(x,y); chmin(ref res,tr.Dist(x,y)+tr.Dist(lca,z)); lca=tr.LCA(y,z); chmin(ref res,tr.Dist(y,z)+tr.Dist(lca,x)); lca=tr.LCA(z,x); chmin(ref res,tr.Dist(z,x)+tr.Dist(lca,y)); WriteLine(res); } } } public class Tree { public List>[] edge; public int Count { get; } public Tree(int num) { Count = num; edge = Enumerable.Repeat(0, num).Select(_ => new List>()).ToArray(); } private static void swap(ref T v1, ref T v2) { var t = v2; v2 = v1; v1 = t; } /// /// 辺を追加します /// /// /// /// public void AddEdge(int u, int v, long weight = 1) { edge[u].Add(new Pair(weight, v)); edge[v].Add(new Pair(weight, u)); } /// /// 木の直径をO(E)で求める /// 依存:Pair /// /// 辺の集合 /// public long Diameter() => Diameter(Diameter(0).v2).v1; private Pair Diameter(int st) { var dist = Enumerable.Repeat(-1L, Count).ToArray(); dist[st] = 0; var que = new Queue(); que.Enqueue(st); var maxj = st; while (que.Any()) { var p = que.Dequeue(); foreach (var e in edge[p]) if (dist[e.v2] == -1) { dist[e.v2] = dist[p] + e.v1; if (dist[maxj] < dist[e.v2]) maxj = e.v2; que.Enqueue(e.v2); } } return new Pair(dist[maxj], maxj); } private List etList; /// /// オイラーツアー /// /// /// /// public List EularTour(int root = 0) { etList = new List(Count * 2); EularTour(root, -1); return etList; } private void EularTour(int index, int pa) { etList.Add(index); foreach (var c in edge[index]) if (c.v2 != pa) EularTour(c.v2, index); etList.Add(index); } private int[][] parent; private int[] depth; private long[] dist; /// /// ダブリングで祖先テーブルを構築します /// 計算量:O(VlogV) /// /// 根 public void LCABuild(int root = 0) { int ct = 0; for (var i = 31; i >= 0; i--) if ((1 & Count >> i) == 1) { ct = i; break; } parent = Enumerable.Repeat(0, ct + 1).Select(_ => Enumerable.Repeat(-1, Count).ToArray()).ToArray(); depth = new int[Count];dist=new long[Count]; LCAdfs(root, -1); for (var i = 1; i <= ct; i++) for (var j = 0; j < Count; j++) if (parent[i - 1][j] != -1) parent[i][j] = parent[i - 1][parent[i - 1][j]]; } private void LCAdfs(int index, int pa) { parent[0][index] = pa; foreach (var e in edge[index]) if (e.v2 != pa) { depth[e.v2] = depth[index] + 1; dist[e.v2]=dist[index]+e.v1; LCAdfs(e.v2, index); } } public long Dist(int u,int v){ return dist[u]+dist[v]-2*dist[LCA(u,v)]; } /// /// 二頂点の最小共通祖先を求めます /// 計算量:O(logV) /// /// /// /// public int LCA(int u, int v) { if (depth[u] > depth[v]) swap(ref u, ref v); for (var i = parent.Length - 1; i >= 0; i--) if ((1 & (depth[v] - depth[u]) >> i) == 1) v = parent[i][v]; if (u == v) return u; for (var i = parent.Length - 1; i >= 0; i--) if (parent[i][u] != parent[i][v]) { u = parent[i][u]; v = parent[i][v]; } return parent[0][u]; } } public class Input { public static string read => ReadLine().Trim(); public static int[] ar => read.Split(' ').Select(int.Parse).ToArray(); public static int num => ToInt32(read); public static long[] arL => read.Split(' ').Select(long.Parse).ToArray(); public static long numL => ToInt64(read); public static T[] create(int n, Func f) => Enumerable.Repeat(0, n).Select(f).ToArray(); public static char[][] grid(int h) => create(h, _ => read.ToCharArray()); public static int[] ar1D(int n) => create(n, _ => num); public static long[] arL1D(int n) => create(n, _ => numL); public static string[] strs(int n) => create(n, _ => read); public static int[][] ar2D(int n) => create(n, _ => ar); public static long[][] arL2D(int n) => create(n, _ => arL); public static List[] edge(int n) => create(n, _ => new List()); public static T GetValue(string g) { var t = typeof(T); if (t == typeof(int)) return (T)(object)int.Parse(g); if (t == typeof(long)) return (T)(object)long.Parse(g); if (t == typeof(string)) return (T)(object)g; if (t == typeof(char)) return (T)(object)char.Parse(g); if (t == typeof(double)) return (T)(object)double.Parse(g); if (t == typeof(bool)) return (T)(object)bool.Parse(g); return default(T); } public static void Make(out T1 v1, out T2 v2) { v1 = Next(); v2 = Next(); } public static void Make(out T1 v1, out T2 v2, out T3 v3) { Make(out v1, out v2); v3 = Next(); } public static void Make(out T1 v1, out T2 v2, out T3 v3, out T4 v4) { Make(out v1, out v2, out v3); v4 = Next(); } public static void Make(out T1 v1, out T2 v2, out T3 v3, out T4 v4, out T5 v5) { Make(out v1, out v2, out v3, out v4); v5 = Next(); } public static void Make(out T1 v1, out T2 v2, out T3 v3, out T4 v4, out T5 v5, out T6 v6) { Make(out v1, out v2, out v3, out v4, out v5); v6 = Next(); } private static Queue sc; public static T Next() { sc = sc ?? new Queue(); if (sc.Count == 0) foreach (var item in read.Split(' ')) sc.Enqueue(item); return GetValue(sc.Dequeue()); } public static void Next(ref T val) => val = Next(); public const long Inf = (long)1e18; public const double eps = 1e-6; public const string Alfa = "abcdefghijklmnopqrstuvwxyz"; public const int MOD = 1000000007; } public class Pair : IComparable> { public T1 v1 { get; set; } public T2 v2 { get; set; } public Pair() { v1 = Input.Next(); v2 = Input.Next(); } public Pair(T1 v1, T2 v2) { this.v1 = v1; this.v2 = v2; } public int CompareTo(Pair p) { var c = Comparer.Default.Compare(v1, p.v1); if (c == 0) c = Comparer.Default.Compare(v2, p.v2); return c; } public override string ToString() => $"{v1.ToString()} {v2.ToString()}"; public override bool Equals(object obj) => this == (Pair)obj; public override int GetHashCode() => v1.GetHashCode() ^ v2.GetHashCode(); public static bool operator ==(Pair p1, Pair p2) => p1.CompareTo(p2) == 0; public static bool operator !=(Pair p1, Pair p2) => p1.CompareTo(p2) != 0; public static bool operator >(Pair p1, Pair p2) => p1.CompareTo(p2) == 1; public static bool operator >=(Pair p1, Pair p2) => p1.CompareTo(p2) != -1; public static bool operator <(Pair p1, Pair p2) => p1.CompareTo(p2) == -1; public static bool operator <=(Pair p1, Pair p2) => p1.CompareTo(p2) != 1; } public class Pair : Pair, IComparable> { public T3 v3 { get; set; } public Pair() : base() { v3 = Input.Next(); } public Pair(T1 v1, T2 v2, T3 v3) : base(v1, v2) { this.v3 = v3; } public int CompareTo(Pair p) { var c = base.CompareTo(p); if (c == 0) c = Comparer.Default.Compare(v3, p.v3); return c; } public override string ToString() => $"{base.ToString()} {v3.ToString()}"; } }