#include #include #include #include #include #define int long long using namespace std; typedef pairpint; typedef vectorvint; #define pb push_back #define mp make_pair #define rep(i,n) for(int i=0;i<(n);i++) templatevoid chmin(T &t,U f){if(t>f)t=f;} templatevoid chmax(T &t,U f){if(t=0;i--){ dat[i]=(dat[i*2+1]+dat[i*2+2])%mod; sum[i]=(sum[i*2+1]+dat[i*2+2])%mod; } } inline void evaluate(int k){ dat[k]=(dat[k]+sum[k]*lazy[k])%mod; if(kseg; int hl_dfs(int v,int p,int d){ par[v]=p; depth[v]=d; heavy[v]=-1; int ma=0,sum=0; rep(i,G[v].size()){ int to=G[v][i]; if(to==p)continue; int val=hl_dfs(to,v,d+1); if(ma=0&&heavy[par[i]]==i)continue; vint s,c; for(int j=i;~j;j=heavy[j]){ head[j]=i; chain[j]=seg.size(); s.pb(S[j]); c.pb(C[j]); } seg.pb(seg_tree()); seg.back().init(s,c); } } int lca(int u,int v){ while(chain[u]!=chain[v]){ if(depth[head[u]]=0)add(par[p],-z); } else{ int x,y; scanf("%lld%lld",&x,&y); x--;y--; int p=lca(x,y); int ans=get(x)+get(y)-get(p); if(par[p]>=0)ans-=get(par[p]); ans=(ans+mod*100)%mod; printf("%lld\n",ans); } } return 0; }