using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; class TEST{ static void Main(){ Sol mySol = new Sol(); mySol.Solve(); } } class Sol{ public void Solve(){ root = 0; lca_init(); nNode = new int[N]; dfs_cnt(); EHeavy = new int[N]; for(int i=0;i>(); dfs_HLDec(); int NHL=HLDec.Count; long[][] sVal = new long[NHL][]; long[][] sSum = new long[NHL][]; for(int i=0;i= mod) sSum[i][j+1] %= mod; } } SegTree[] ST=new SegTree[NHL]; for(int i=0;i= mod) sum -= mod; sum += sSum[Compo[a]][Idx[a]+1] - sSum[Compo[a]][0] + mod; while(sum >= mod) sum -= mod; a = HLDec[Compo[a]][0]; a = parent[0][a]; } while(Compo[b] != Compo[c]){ sum += ST[Compo[b]].QuerySum(0,Idx[b]+1); if(sum >= mod) sum -= mod; sum += sSum[Compo[b]][Idx[b]+1] - sSum[Compo[b]][0] + mod; while(sum >= mod) sum -= mod; b = HLDec[Compo[b]][0]; b = parent[0][b]; } if(Idx[b] < Idx[a]){ int tmp = a; a = b; b = tmp; } sum += ST[Compo[c]].QuerySum(Idx[a],Idx[b]+1); if(sum >= mod) sum -= mod; sum += sSum[Compo[c]][Idx[b]+1] - sSum[Compo[c]][Idx[a]] + mod; while(sum >= mod) sum -= mod; sb.AppendLine(sum.ToString()); } } Console.Write(sb.ToString()); } int N; long[] S,C; List[] E; int Q; List[] Query; static long mod = (long)1e9+7; int[][] parent; int[] depth; static int lmax=24; int root; int[] nNode; int[] EHeavy; int[] Compo; int[] Idx; List> HLDec; struct Triple{ public int node,compo,idx; public Triple(int n_,int c_,int i_){ node=n_;compo=c_;idx=i_; } } void dfs_HLDec(){ //Console.WriteLine("now={0},cmp={1},idx={2}",now,cmp,idx); Stack Stk=new Stack(); Stk.Push(new Triple(root,0,0)); Compo[0]=0; Idx[0]=0; HLDec.Add(new List()); HLDec[0].Add(0); //cmp=1; while(Stk.Count>0){ var p=Stk.Pop(); int now=p.node; int c=p.compo; int idx=p.idx; //Console.WriteLine(now+" "+c+" "+idx); int max=0;int trgt=-1; foreach(var nxt in E[now]){ if(nxt==parent[0][now])continue; if(max()); Compo[nxt]=HLDec.Count-1; Idx[nxt]=0; HLDec[Compo[nxt]].Add(nxt); Stk.Push(new Triple(nxt,Compo[nxt],0)); } if(nxt==EHeavy[now]){ Compo[nxt]=c; Idx[nxt]=idx+1; HLDec[Compo[nxt]].Add(nxt); Stk.Push(new Triple(nxt,c,idx+1)); } } } } class Pair{ public int node,depth; public Pair(int n_,int d_){ node=n_;depth=d_; } } void dfs_cnt(){ Pair[] P=new Pair[N]; for(int i=0;ix.depth>y.depth?-1:x.depthdepth[v])return lca(v,u); for(int i=0;i>i)&1) >0 ){ v=parent[i][v]; } } if(u==v)return u; for(int i=lmax-1;i>=0;i--){ if(parent[i][u]!=parent[i][v]){ u=parent[i][u]; v=parent[i][v]; } } return parent[0][u]; } void bfs(int strt,int dep_strt){ Queue Q=new Queue(); parent[0][strt]=-1;depth[strt]=0; Q.Enqueue(strt); while(Q.Count>0){ int now=Q.Dequeue(); int par=parent[0][now]; foreach(int v in E[now]){ if(v!=par){ parent[0][v]=now;depth[v]=depth[now]+1; Q.Enqueue(v); } } } } public Sol(){ using (var r = new FastIn(100000)){ N = r.ReadInt(); S = new long[N]; for(int i=0;i[N]; for(int i=0;i(); } for(int i=0;i[Q]; for(int i=0;i(4); Query[i].Add(r.ReadInt()); Query[i].Add(r.ReadInt()-1); Query[i].Add(r.ReadInt()-1); if(Query[i][0] == 0){ Query[i].Add(r.ReadInt()); } } } } static String rs(){return Console.ReadLine();} static int ri(){return int.Parse(Console.ReadLine());} static long rl(){return long.Parse(Console.ReadLine());} static double rd(){return double.Parse(Console.ReadLine());} static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);} static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));} static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));} static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));} } class SegTree{ //segment Tree // 0-origin long[] Data; // long[] Lazy; long[] Coef; long Inf; //largeNumber int N; //size public int n; //size (2) static long mod = (long)1e9+7; public SegTree(int n_){ N=n_;Inf=0; n=1; while(n0){ k=(k-1)/2; Coef[k] = Coef[k*2+1] + Coef[k*2+2]; if(Coef[k] >= mod) Coef[k] -= mod; } } public long QuerySum(int a,int b){ QuerySumRet = 0; QueryWithLazy(a,b,0,0,n); return QuerySumRet; } long QuerySumRet; public long QueryWithLazy(int a,int b,int k,int l,int r){ //Console.WriteLine("in query:a={0},b={1},k={2},l={3},r={4}",a,b,k,l,r); // No intersection if(r<=a || b<=l) return Inf; if(a<=l && r<=b){ // [l,r) is included in [a,b) long inc = Coef[k] * Lazy[k] + Data[k]; if(inc >= mod) inc %= mod; QuerySumRet += inc; if(QuerySumRet >= mod) QuerySumRet -= mod; return Coef[k]; } long cl=QueryWithLazy(a,b,k*2+1,l,(l+r)/2); long cr=QueryWithLazy(a,b,k*2+2,(l+r)/2,r); long clr = cl + cr; long ret = Lazy[k] * clr; if(ret >= mod) ret %= mod; QuerySumRet += ret; if(QuerySumRet >= mod) QuerySumRet -= mod; return clr; } public void AddRange(int a,int b,long val,int k,int l,int r){ // [a,b) [l,r) Data[k]+val if(r<=a || b<=l) return; if(a<=l && r<=b){ Lazy[k] += val; if(Lazy[k] >= mod) Lazy[k] -= mod; long inc = val * Coef[k]; if(inc >= mod) inc %= mod; while(k>0){ k=(k-1)/2; Data[k] += inc; if(Data[k] >= mod) Data[k] -= mod; } return; } AddRange(a,b,val,k*2+1,l,(l+r)/2); AddRange(a,b,val,k*2+2,(l+r)/2,r); } public void UniqInit(int val){ for(int i=0+n-1;i0){ l=(l-1)/2;r=(r-1)/2; for(int i=l;i<=r;i++)Data[i]=val; } } public void Dump(){ Console.WriteLine(); int h=0; int cnt=0; for(int i=0;i