#include #include #include #include using namespace std; typedef long long ll; #define M 1000000007 int n,k,q,sz[200005],id[200005],vs[200005],hv[200005],hd[2000005],cn[200005],dp[200005]; ll s[2000005],c[200005]; vectorg[200005]; ll seg[1<<20],la[1<<20],sec[1<<20]; void dfs1(int v,int p){ sz[v]=1; hv[v]=-1; for(int i=0;i0){ o=(o-1)/2; sec[o]=(sec[o*2+1]+sec[o*2+2])%M; } } void in2(int o,ll x){ o+=(1<<19)-1; seg[o]+=x; while(o>0){ o=(o-1)/2; seg[o]=(seg[o*2+1]+seg[o*2+2])%M; } } void lazy(int r,int l,int o){ seg[o]=(seg[o]+sec[o]*la[o]%M)%M; if(l-r>0){ la[o*2+1]=(la[o*2+1]+la[o])%M; la[o*2+2]=(la[o*2+2]+la[o])%M; } la[o]=0; } void add(int a,int b,int r,int l,int o,ll x){ lazy(r,l,o); if(bdp[hd[v]]){ add(hd[u],u,0,(1<<19)-1,0,z); u=cn[u]; }else{ add(hd[v],v,0,(1<<19)-1,0,z); v=cn[v]; } } add(min(u,v),max(u,v),0,(1<<19)-1,0,z); }else{ ll ans=0; while(hd[u]!=hd[v]){ if(dp[hd[u]]>dp[hd[v]]){ ans=(ans+sum(hd[u],u,0,(1<<19)-1,0))%M; u=cn[u]; }else{ ans=(ans+sum(hd[v],v,0,(1<<19)-1,0))%M; v=cn[v]; } } ans=(ans+sum(min(u,v),max(u,v),0,(1<<19)-1,0))%M; printf("%lld\n",ans); } } }