Find tree

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define mp make_pair
using namespace std;
const int N=100002;
const int deepmax=20;
const long long P=1000000007;
int n,m,SZ,center;
int a[N],b[N],par[N],deep[N];
long long A[deepmax][N],B[deepmax][N],Br[deepmax][N];
bool fix[N];
vector <int> v[N];

int input(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
    for (int i=2,x,y;i<=n;i++){
        scanf("%d%d",&x,&y);
        v[x].pb(y);
        v[y].pb(x);
    }
    return 0;
}

int fin(int x,int from){
    int S=1;
    for (int i=0;i<v[x].size();i++)
    if (v[x][i]!=from)
        if (!fix[v[x][i]])
        S+=fin(v[x][i],x);
    if (S*2>=SZ && center==0) center=x;
    return S;
}

void dfs(int x,int from,int d){
    B[d][x]=(B[d][from]*a[x]+b[x])%P;
    Br[d][x]=(A[d][from]*b[x]+Br[d][from])%P;
    A[d][x]=A[d][from]*a[x]%P;
    for (int i=0;i<v[x].size();i++)
    if (v[x][i]!=from)
        if (!fix[v[x][i]])
        dfs(v[x][i],x,d);
}

void pre(int x,int from){
    SZ=fin(x,x);
    center=0;
    fin(x,x);
    x=center;

    par[x]=from;
    deep[x]=deep[from]+1;
    fix[x]=1;

    A[deep[x]][x]=1;
    B[deep[x]][x]=Br[deep[x]][x]=0;

    for (int i=0;i<v[x].size();i++)
    if (!fix[v[x][i]])
        dfs(v[x][i],x,deep[x]),
        pre(v[x][i],x);
}

int LCA(int x,int y){
    while (deep[x]>deep[y]) x=par[x];
    while (deep[x]<deep[y]) y=par[y];
    while (x!=y) x=par[x],y=par[y];
    return x;
}

int sol(){
    pre(1,0);
    int x,y,z;
    long long ans=0;
    while (m--){
        scanf("%d%d%d",&x,&y,&z);
        ans=z;
        z=LCA(x,y);
        ans=(ans*A[deep[z]][x]+Br[deep[z]][x])%P;
        ans=(ans*a[z]+b[z])%P;
        ans=(ans*A[deep[z]][y]+B[deep[z]][y])%P;
        printf("%lld\n",ans);
    }
    return 0;
}

int main() {
    input();
    sol();
    return 0;
}