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 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]; var h=new long[n+1]; for(int i=1;i<=n;i++){li[i]=new List();} for(int i=0;i[] li; private List lir; private List> lia=new List>(),lib=new List>(); private int[] da,ea,fa,ia,va; private St[] st; private St stt; private int n,m=0,o,r,f=0,hc=0; public Hld(List[] li,int o,bool bo){ if(!bo){hc=1;} this.li=li; n=li.Length; this.o=o; fa=new int[n]; da=new int[n]; ea=new int[n]; va=new int[n]; lir=new List(); Fu1(o); r=da[o]; fa=new int[m]; ia=new int[m]; st=new St[m]; stt=new St(m); for(int i = 0;i=0){st[da[a]].Ud2(0,ea[a]-hc,d);} if(va[a]!=-1){stt.Ud2(ia[da[a]]+1,va[a],d);} } public void Ud(int a,long d){ st[da[a]].Ud(ea[a],d); } public long Get(int a,int b){ long p=0; int af=fa[da[a]],bf=fa[da[b]]; while(af>bf){ p=Fg(p,da[a],ea[a],lia[da[a]].Count-1); p=Fgt(p,ia[da[a]],lia[da[a]].Count-ea[a]); 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==a){ 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