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 c=sc.Ia; var d=sc.Ia; 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>(); 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=Fg(p,da[a],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;i=m;i--){dat[i]=new Dt(true);} for(int i=m-1;i>=0;i--){dat[i]=(i<<1)+1>1; while(q>=0){ Dt o=Dt.Cm(dat[(q<<1)+1],dat[(q<<1)+2]); if(dat[q]==o){break;} dat[q]=o; q=(q-1)>>1; } } private Dt Fdg(int a,int b,int k,int l,int r){ if(dat[k].c1!=0){Fde(k,Dt.e);} if(r>1); Dt q=Fdg(a,b,k*2+2,(l+r+1)>>1,r); return Dt.Cm(p,q); } public long Get(int a,int b){return a>b?0:Fdg(a,b,0,0,m).d1;} public void Ud2(int a,int b,long d){Hn(a,b,0,0,m,d);} private void Hn(int a,int b,int k,int l,int r,long d){ if(a<=l&&r<=b){Fde(k,d);return;} else if(dat[k].c1!=0){Fde(k,Dt.e);} if(r>=a&&b>=l){ Hn(a,b,k*2+1,l,(l+r)>>1,d); Hn(a,b,k*2+2,(l+r+1)>>1,r,d); dat[k]=Dt.Cm(dat[(k<<1)+1],dat[(k<<1)+2]); } } private void Fde(int k,long d){ dat[k]=Dt.Dm(dat[k],d); dat[k]=Dt.Um(dat[k],dat[k].c1); if((k<<1)+2<=cnt){dat[(k<<1)+1]=Dt.Dm(dat[(k<<1)+1],dat[k].c1);} if((k<<1)+2(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