using System; using System.Collections.Generic; using System.Collections; using System.Collections.Specialized; using System.Linq; using System.Text; using System.IO; using System.Reflection; using static System.Math; using System.Numerics; static class Program{ const int mod=(int)1e9+7; static List[] li; static bool[] b; static int[] h; static void Main(){ Sc sc=new Sc(); var s=sc.Ia; int n=s[0],m=n-1; li=new List[n+1]; b=new bool[n+1]; h=new int[n+1]; for(int i=1;i<=n;i++){li[i]=new List();} for(int i=0;i0;i--) { p+=g[i]; ans+=p*i; } Console.WriteLine("{0}",ans); } } public class Hld{ private List[] li; private List lir; private List> lia=new List>(); private List> lib=new List>(); private int[] ba,da,ea,fa; private St[] st; private int n,m=0,o,r=-1; public Hld(List[] li,int n,int o){ this.li=li; this.n=n; this.o=o; ba=new int[n+1]; da=new int[n+1]; ea=new int[n+1]; lir=new List(); Fu1(o); r=da[o]; fa=new int[m]; st=new St[m]; for(int i = 0;ibf){ p+=st[da[a]].Get(ea[a],lia[da[a]].Count-1); a=lir[da[a]]; af--; } while(afbf){ st[da[a]].Ud2(ea[a],lia[da[a]].Count-1,d); a=lir[da[a]]; af--; } while(af()); lib.Add(new List()); lir.Add(0); lia[m].Add(a); da[a]=m; m++; } else{ ea[a]=lia[da[p]].Count; lia[da[p]].Add(a); da[a]=da[p]; if(li[a].Count>2||o==1){ for(int i=0;i0){dat[(q-1)>>1]=dat[(q-1)>>1]+b;q=(q-1)>>1;} } private long Fdg(int a,int b,int k,int l,int r){ if(dat2[k]!=0){ dat[k]+=dat2[k]; if(2*k+1>1;} if(2*k+2>1;} dat2[k]=0; } if(r>1)+Fdg(a,b,k*2+2,(l+r+1)>>1,r);} } public long Get(int a,int b){return Fdg(a,b,0,0,m-1);} public void Ud2(int a,int b,long d){Hn(a,b,0,0,m-1,d*m);} private long Hn(int a,int b,int k,int l,int r,long d){ if(a<=l&&r<=b){dat2[k]+=d;return d;} else if(r>=a&&b>=l){ long q=Hn(a,b,k*2+1,l,(l+r)>>1,d>>1)+Hn(a,b,k*2+2,(l+r+1)>>1,r,d>>1); dat[k]+=q; return q; } return 0; } } public class Sc{ public int I{get{return int.Parse(Console.ReadLine());}} public long L{get{return long.Parse(Console.ReadLine());}} public double D{get{return double.Parse(Console.ReadLine());}} public string S{get{return Console.ReadLine();}} public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}} public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}} public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}} public string[] Sa{get{return Console.ReadLine().Split();}} public object[] Oa{get{return Console.ReadLine().Split();}} public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}} public int[] Ia3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),int.Parse);} public int[] Ia3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),int.Parse);} public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}} public long[] La3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),long.Parse);} public long[] La3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),long.Parse);} public double[] Da2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),double.Parse);}} public double[] Da3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),double.Parse);} public double[] Da3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),double.Parse);} public T[] Arr(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i