In this HackerRank White Falcon And Tree problem solution, you are given a tree with N nodes. and each node contains a linear function. and first, we need to assign the ax + b function of all the nodes on the path and then calculate the modulo of the function with the given expression.

HackerRank White Falcon And Tree problem solution


Problem solution in Java Programming.

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Solution {
    
    static InputStream is;
    static PrintWriter out;
    static String INPUT = "";
    static int mod = 1000000007;
    
    static void solve()
    {
        int n = ni();
        int[][] co = new int[n][];
        for(int i = 0;i < n;i++){
            co[i] = new int[]{ni(), ni()};
        }
        int[] from = new int[n-1];
        int[] to = new int[n-1];
        for(int i = 0;i < n-1;i++){
            from[i] = ni()-1;
            to[i] = ni()-1;
        }
        int[][] g = packU(n, from, to);
        int[][] pars = parents3(g, 0);
        int[] par = pars[0], ord = pars[1], dep = pars[2];
        int[] clus = decomposeToHeavyLight(g, par, ord);
        int[][] cluspath = clusPaths(clus, ord);
        int[] clusiind = clusIInd(cluspath, n);
        SegmentTreeNodePlus[] sts = new SegmentTreeNodePlus[cluspath.length];
        for(int i = 0;i < cluspath.length;i++){
            int[][] lco = new int[cluspath[i].length][];
            for(int j = 0;j < cluspath[i].length;j++){
                lco[j] = co[cluspath[i][j]];
            }
            sts[i] = new SegmentTreeNodePlus(lco);
        }
        
        int[][] spar = logstepParents(par);
        int Q = ni();
        for(int z = 0;z < Q;z++){
            int t = ni();
            if(t == 1){
                int u = ni()-1, v = ni()-1, a = ni(), b = ni();
                int lca = lca2(u, v, spar, dep);
                int[][] pr = query2(u, lca, v, clus, cluspath, clusiind, par);
                for(int[] e : pr){
                    sts[e[0]].update(Math.min(e[1], e[2]), Math.max(e[1], e[2])+1, a, b);
                }
            }else{
                int u = ni()-1, v = ni()-1;
                long x = ni();
                int lca = lca2(u, v, spar, dep);
                int[][] pr = query2(u, lca, v, clus, cluspath, clusiind, par);
                for(int[] e : pr){
                    if(e[1] <= e[2]){
                        x = sts[e[0]].apply(e[1], e[2]+1, x, false);
                    }else{
                        x = sts[e[0]].apply(e[2], e[1]+1, x, true);
                    }
                }
                out.println(x);
            }
        }
    }
    
    public static int lca2(int a, int b, int[][] spar, int[] depth) {
        if (depth[a] < depth[b]) {
            b = ancestor(b, depth[b] - depth[a], spar);
        } else if (depth[a] > depth[b]) {
            a = ancestor(a, depth[a] - depth[b], spar);
        }

        if (a == b)
            return a;
        int sa = a, sb = b;
        for (int low = 0, high = depth[a], t = Integer.highestOneBit(high), k = Integer
                .numberOfTrailingZeros(t); t > 0; t >>>= 1, k--) {
            if ((low ^ high) >= t) {
                if (spar[k][sa] != spar[k][sb]) {
                    low |= t;
                    sa = spar[k][sa];
                    sb = spar[k][sb];
                } else {
                    high = low | t - 1;
                }
            }
        }
        return spar[0][sa];
    }

    protected static int ancestor(int a, int m, int[][] spar) {
        for (int i = 0; m > 0 && a != -1; m >>>= 1, i++) {
            if ((m & 1) == 1)
                a = spar[i][a];
        }
        return a;
    }

    public static int[][] logstepParents(int[] par) {
        int n = par.length;
        int m = Integer.numberOfTrailingZeros(Integer.highestOneBit(n - 1)) + 1;
        int[][] pars = new int[m][n];
        pars[0] = par;
        for (int j = 1; j < m; j++) {
            for (int i = 0; i < n; i++) {
                pars[j][i] = pars[j - 1][i] == -1 ? -1
                        : pars[j - 1][pars[j - 1][i]];
            }
        }
        return pars;
    }
    
    public static class SegmentTreeNodePlus {
        public int M, H, N;
        public Node[] node;
        public int[][] cover;
        
        private static class Node
        {
            long co;
            long lc;
            long rc;
            
            public Node() {
                co = 1;
                lc = rc = 0;
            }

            public Node(long co, long lc, long rc) {
                this.co = co;
                this.lc = lc;
                this.rc = rc;
            }
            
            public long apply(long x, boolean dir)
            {
                if(!dir){
                    return (co * x + lc) % mod;
                }else{
                    return (co * x + rc) % mod;
                }
            }
        }
        
        public SegmentTreeNodePlus(int[][] co)
        {
            N = co.length;
            M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
            H = M>>>1;
            
            node = new Node[M];
            cover = new int[H][];
            for(int i = 0;i < N;i++){
                node[H+i] = new Node(co[i][0], co[i][1], co[i][1]);
            }
            for(int i = H-1;i >= 1;i--)propagate(i);
        }
        
        private void propagate(int cur)
        {
            node[cur] = prop2(node[2*cur], node[2*cur+1], cover[cur], node[cur], H/Integer.highestOneBit(cur));
        }
        
        static final int mod = 1000000007;
        
        private Node prop2(Node L, Node R, int[] cover, Node C, int len)
        {
            if(L != null && R != null){
                if(C == null)C = new Node();
                if(cover == null){
                    C.co = L.co * R.co % mod;
                    C.lc = (R.co * L.lc + R.lc) % mod;
                    C.rc = (L.co * R.rc + L.rc) % mod;
                }else{
                    long co = cover[0], c = cover[1];
                    for(int x = len;x > 1;x >>>= 1){
                        long nco = co * co % mod;
                        long nc = (co * c + c) % mod;
                        co = nco;
                        c = nc;
                    }
                    C.co = co;
                    C.lc = C.rc = c;
                }
                return C;
            }else if(L != null){
                return prop1(L, cover, C, len);
            }else if(R != null){
                return prop1(R, cover, C, len);
            }else{
                return null;
            }
        }
        
        private Node prop1(Node L, int[] cover, Node C, int len)
        {
            if(C == null)C = new Node();
            if(cover == null){
                C.co = L.co;
                C.lc = L.lc;
                C.rc = L.rc;
            }else{
                long co = cover[0], c = cover[1];
                for(int x = len;x > 1;x >>>= 1){
                    long nco = co * co % mod;
                    long nc = (co * c + c) % mod;
                    co = nco;
                    c = nc;
                }
                C.co = co;
                C.lc = C.rc = c;
            }
            return C;
        }
        
        int[] temp = null;
        
        public void update(int l, int r, int a, int b) { 
            temp = new int[]{a, b};
            if(l < r)update(l, r, a, b, 0, H, 1); }
        
        protected void update(int l, int r, int a, int b, int cl, int cr, int cur)
        {
            if(cur >= H){
                node[cur].co = a;
                node[cur].lc = node[cur].rc = b;
            }else if(l <= cl && cr <= r){
                cover[cur] = temp;
                propagate(cur);
            }else{
                int mid = cl+cr>>>1;
                boolean bp = false;
                if(cover[cur] != null){
                    if(2*cur < H){
                        cover[2*cur] = cover[cur];
                        cover[2*cur+1] = cover[cur];
                        cover[cur] = null;
                        bp = true;
                    }else{
                        node[2*cur].co = cover[cur][0];
                        node[2*cur].lc = node[2*cur].rc = cover[cur][1];
                        node[2*cur+1].co = cover[cur][0];
                        node[2*cur+1].lc = node[2*cur+1].rc = cover[cur][1];
                        cover[cur] = null;
                    }
                }
                if(cl < r && l < mid){
                    update(l, r, a, b, cl, mid, 2*cur);
                }else if(bp){
                    propagate(2*cur);
                }
                
                if(mid < r && l < cr){
                    update(l, r, a, b, mid, cr, 2*cur+1);
                }else if(bp){
                    propagate(2*cur+1);
                }
                propagate(cur);
            }
        }
        
        public long apply(int l, int r, long x, boolean dir) {
            return apply(l, r, x, dir, 0, H, 1);
        }
        
        protected long apply(int l, int r, long x, boolean dir, int cl, int cr, int cur)
        {
            if(l <= cl && cr <= r){
                return node[cur].apply(x, dir);
            }else{
                int mid = cl+cr>>>1;
                if(cover[cur] != null){
                    long co = cover[cur][0], c = cover[cur][1];
                    for(int h = Math.min(r, cr) - Math.max(l, cl);h > 0;h >>>= 1){
                        if((h&1) == 1){
                            x = (co * x + c) % mod;
                        }
                        long nco = co * co % mod;
                        long nc = (co * c + c) % mod;
                        co = nco;
                        c = nc;
                    }
                    return x;
                }
                if(!dir){
                    if(cl < r && l < mid){
                        x = apply(l, r, x, dir, cl, mid, 2*cur);
                    }
                    if(mid < r && l < cr){
                        x = apply(l, r, x, dir, mid, cr, 2*cur+1);
                    }
                }else{
                    if(mid < r && l < cr){
                        x = apply(l, r, x, dir, mid, cr, 2*cur+1);
                    }
                    if(cl < r && l < mid){
                        x = apply(l, r, x, dir, cl, mid, 2*cur);
                    }
                }
                return x;
            }
        }
    }
    
    public static int[][] parents3(int[][] g, int root) {
        int n = g.length;
        int[] par = new int[n];
        Arrays.fill(par, -1);

        int[] depth = new int[n];
        depth[0] = 0;

        int[] q = new int[n];
        q[0] = root;
        for (int p = 0, r = 1; p < r; p++) {
            int cur = q[p];
            for (int nex : g[cur]) {
                if (par[cur] != nex) {
                    q[r++] = nex;
                    par[nex] = cur;
                    depth[nex] = depth[cur] + 1;
                }
            }
        }
        return new int[][] { par, q, depth };
    }
    
    public static int[] decomposeToHeavyLight(int[][] g, int[] par, int[] ord)
    {
        int n = g.length;
        int[] size = new int[n];
        Arrays.fill(size, 1);
        for(int i = n-1;i > 0;i--)size[par[ord[i]]] += size[ord[i]];
        
        int[] clus = new int[n];
        Arrays.fill(clus, -1);
        int p = 0;
        outer:
        for(int i = 0;i < n;i++){
            int u = ord[i];
            if(clus[u] == -1)clus[u] = p++;
            for(int v : g[u]){
                if(par[u] != v && size[v] >= size[u]/2){
                    clus[v] = clus[u];
                    continue outer;
                }
            }
            for(int v : g[u]){
                if(par[u] != v){
                    clus[v] = clus[u];
                    break;
                }
            }
        }
        return clus;
    }
    
    public static int[][] clusPaths(int[] clus, int[] ord)
    {
        int n = clus.length;
        int[] rp = new int[n];
        int sup = 0;
        for(int i = 0;i < n;i++){
            rp[clus[i]]++;
            sup = Math.max(sup, clus[i]);
        }
        sup++;
        
        int[][] row = new int[sup][];
        for(int i = 0;i < sup;i++)row[i] = new int[rp[i]];
        
        for(int i = n-1;i >= 0;i--){
            row[clus[ord[i]]][--rp[clus[ord[i]]]] = ord[i];
        }
        return row;
    }
    
    public static int[] clusIInd(int[][] clusPath, int n)
    {
        int[] iind = new int[n];
        for(int[] path : clusPath){
            for(int i = 0;i < path.length;i++){
                iind[path[i]] = i;
            }
        }
        return iind;
    }
    
    public static int[][] query2(int x, int anc, int y, int[] clus, int[][] cluspath, int[] clusiind, int[] par)
    {
        int[][] stack = new int[60][];
        int sp = 0;
        
        int cx = clus[x]; 
        int indx = clusiind[x]; 
        while(cx != clus[anc]){
            stack[sp++] = new int[]{cx, indx, 0};
            int con = par[cluspath[cx][0]];
            indx = clusiind[con];
            cx = clus[con];
        }
        stack[sp++] = new int[]{cx, indx, clusiind[anc]};
        
        int top = sp;
        int cy = clus[y];
        int indy = clusiind[y]; 
        while(cy != clus[anc]){
            stack[sp++] = new int[]{cy, 0, indy};
            int con = par[cluspath[cy][0]];
            indy = clusiind[con];
            cy = clus[con];
        }
        if(clusiind[anc] < indy){
            stack[sp++] = new int[]{cy, clusiind[anc]+1, indy};
        }
        for(int p = top, q = sp-1;p < q;p++,q--){
            int[] dum = stack[p]; stack[p] = stack[q]; stack[q] = dum;
        }
        return Arrays.copyOf(stack, sp);
    }
    
    static int[][] packU(int n, int[] from, int[] to) {
        int[][] g = new int[n][];
        int[] p = new int[n];
        for (int f : from)
            p[f]++;
        for (int t : to)
            p[t]++;
        for (int i = 0; i < n; i++)
            g[i] = new int[p[i]];
        for (int i = 0; i < from.length; i++) {
            g[from[i]][--p[from[i]]] = to[i];
            g[to[i]][--p[to[i]]] = from[i];
        }
        return g;
    }
    
    public static void main(String[] args) throws Exception
    {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        out = new PrintWriter(System.out);
        
        solve();
        out.flush();
    }
    
    private static boolean eof()
    {
        if(lenbuf == -1)return true;
        int lptr = ptrbuf;
        while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
        
        try {
            is.mark(1000);
            while(true){
                int b = is.read();
                if(b == -1){
                    is.reset();
                    return true;
                }else if(!isSpaceChar(b)){
                    is.reset();
                    return false;
                }
            }
        } catch (IOException e) {
            return true;
        }
    }
    
    private static byte[] inbuf = new byte[1024];
    static int lenbuf = 0, ptrbuf = 0;
    
    private static int readByte()
    {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }
    
    private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
    private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
    
    private static double nd() { return Double.parseDouble(ns()); }
    private static char nc() { return (char)skip(); }
    
    private static String ns()
    {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    
    private static char[] ns(int n)
    {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }
    
    private static char[][] nm(int n, int m)
    {
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }
    
    private static int[] na(int n)
    {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }
    
    private static int ni()
    {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private static long nl()
    {
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
}


Problem solution in C++ programming.

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long,long long> pll; typedef vector<pair<long long,long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

template<int MOD>
struct ModInt {
    static const int Mod = MOD;
    unsigned x;
    ModInt(): x(0) { }
    ModInt(signed sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
    ModInt(signed long long sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
    int get() const { return (int)x; }
    
    ModInt &operator+=(ModInt that) { if((x += that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator-=(ModInt that) { if((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
    
    ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
    ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
    ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
};
typedef ModInt<1000000007> mint;

//y = ax + b
struct LinearExpr {
    mint a, b;
    LinearExpr(): a(1), b(0) { }
    LinearExpr(mint a_, mint b_): a(a_), b(b_) { }
    LinearExpr(const LinearExpr &val, int) { a = val.a, b = val.b; }
    LinearExpr &operator+=(const LinearExpr &that) {
        b = b * that.a + that.b;
        a = a * that.a;
        return *this;
    }
    LinearExpr operator+(const LinearExpr &that) const {
        return LinearExpr(*this) += that;
    }
    LinearExpr operator*(int k) const {
        LinearExpr a = *this, r;
        while(k) {
            if(k & 1) r += a;
            a += a;
            k >>= 1;
        }
        return r;
    }
    mint evalute(mint x) const { return a * x + b; }
};

typedef LinearExpr Val;

struct Sum {
    LinearExpr forward, backward;
    Sum(): forward(), backward() { }
    Sum(const Val &val, int): forward(val), backward(val) { }
    Sum &operator+=(const Sum &that) {
        forward += that.forward;
        backward = that.backward + backward;
        return *this;
    }
    Sum operator+(const Sum &that) const { return Sum(*this) += that; }
};

struct Laziness {
    bool fill;
    LinearExpr expr;
    Laziness(): fill(false) { }
    Laziness(LinearExpr expr_): fill(true), expr(expr_) { }
    Laziness &operator+=(const Laziness &that) {
        if(that.fill)
            *this = that;
        return *this;
    }
    void addToVal(Val &val, int) const {
        if(fill)
            val = expr;
    }
    void addToSum(Sum &sum, int left, int right) const {
        if(fill) {
            LinearExpr multiplicated = expr * (right - left);
            sum.forward = sum.backward = multiplicated;
        }
    }
};

struct SegmentTree {
    vector<Val> leafs;
    vector<Sum> nodes;
    vector<Laziness> laziness;
    vector<int> leftpos, rightpos;
    int n, n2;
    void init(int n_, const Val &v = Val()) { init(vector<Val>(n_, v)); }
    void init(const vector<Val> &u) {
        n = 1; while(n < (int)u.size()) n *= 2;
        n2 = (n - 1) / 2 + 1;
        leafs = u; leafs.resize(n, Val());
        nodes.resize(n);
        for(int i = n-1; i >= n2; -- i)
            nodes[i] = Sum(leafs[i*2-n], i*2-n) + Sum(leafs[i*2+1-n], i*2+1-n);
        for(int i = n2-1; i > 0; -- i)
            nodes[i] = nodes[i*2] + nodes[i*2+1];
        laziness.assign(n, Laziness());

        leftpos.resize(n); rightpos.resize(n);
        for(int i = n-1; i >= n2; -- i) {
            leftpos[i] = i*2-n;
            rightpos[i] = (i*2+1-n) + 1;
        }
        for(int i = n2-1; i > 0; -- i) {
            leftpos[i] = leftpos[i*2];
            rightpos[i] = rightpos[i*2+1];
        }
    }
    Val get(int i) {
        int indices[128];
        int k = getIndices(indices, i, i+1);
        propagateRange(indices, k);
        return leafs[i];
    }
    Sum getRangeCommutative(int i, int j) {
        int indices[128];
        int k = getIndices(indices, i, j);
        propagateRange(indices, k);
        Sum res = Sum();
        for(int l = i + n, r = j + n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) res += sum(l ++);
            if(r & 1) res += sum(-- r);
        }
        return res;
    }
    Sum getRange(int i, int j) {
        int indices[128];
        int k = getIndices(indices, i, j);
        propagateRange(indices, k);
        Sum res = Sum();
        for(; i && i + (i&-i) <= j; i += i&-i)
            res += sum((n+i) / (i&-i));
        for(k = 0; i < j; j -= j&-j)
            indices[k ++] = (n+j) / (j&-j) - 1;
        while(-- k >= 0) res += sum(indices[k]);
        return res;
    }
    void set(int i, const Val &x) {
        int indices[128];
        int k = getIndices(indices, i, i+1);
        propagateRange(indices, k);
        leafs[i] = x;
        mergeRange(indices, k);
    }
    void addToRange(int i, int j, const Laziness &x) {
        if(i >= j) return;
        int indices[128];
        int k = getIndices(indices, i, j);
        propagateRange(indices, k);
        int l = i + n, r = j + n;
        if(l & 1) { int p = (l ++) - n; x.addToVal(leafs[p], p); }
        if(r & 1) { int p = (-- r) - n; x.addToVal(leafs[p], p); }
        for(l >>= 1, r >>= 1; l < r; l >>= 1, r >>= 1) {
            if(l & 1) laziness[l ++] += x;
            if(r & 1) laziness[-- r] += x;
        }
        mergeRange(indices, k);
    }
private:
    int getIndices(int indices[], int i, int j) const {
        int k = 0, l, r;
        if(i >= j) return 0;
        for(l = (n + i) >> 1, r = (n + j - 1) >> 1; l != r; l >>= 1, r >>= 1) {
            indices[k ++] = l;
            indices[k ++] = r;
        }
        for(; l; l >>= 1) indices[k ++] = l;
        return k;
    }
    void propagateRange(int indices[], int k) {
        for(int i = k - 1; i >= 0; -- i)
            propagate(indices[i]);
    }
    void mergeRange(int indices[], int k) {
        for(int i = 0; i < k; ++ i)
            merge(indices[i]);
    }
    inline void propagate(int i) {
        if(i >= n) return;
        laziness[i].addToSum(nodes[i], leftpos[i], rightpos[i]);
        if(i * 2 < n) {
            laziness[i * 2] += laziness[i];
            laziness[i * 2 + 1] += laziness[i];
        }else {
            laziness[i].addToVal(leafs[i * 2 - n], i * 2 - n);
            laziness[i].addToVal(leafs[i * 2 + 1 - n], i * 2 + 1 - n);
        }
        laziness[i] = Laziness();
    }
    inline void merge(int i) {
        if(i >= n) return;
        nodes[i] = sum(i * 2) + sum(i * 2 + 1);
    }
    inline Sum sum(int i) {
        propagate(i);
        return i < n ? nodes[i] : Sum(leafs[i - n], i - n);
    }
};

struct CentroidPathDecomposition {
    vector<int> colors, positions;    //Vertex -> Color, Vertex -> Offset
    vector<int> lengths, parents, branches;    //Color -> Int, Color -> Color, Color -> Offset
    vector<int> parentnodes, depths;    //Vertex -> Vertex, Vertex -> Int
    //vector<FenwickTree>??????1??????????
    //sortednodes?[lefts[v], rights[v])?v?subtree??????
    vector<int> sortednodes, offsets;    //Index -> Vertex, Color -> Index
    vector<int> lefts, rights;    //Vertex -> Index

    struct BuildDFSState {
        int i, len, parent;
        BuildDFSState() { }
        BuildDFSState(int i_, int l, int p): i(i_), len(l), parent(p) { }
    };

    //??????????????????????????
    void build(const vector<vi> &g, int root) {
        int n = g.size();

        colors.assign(n, -1); positions.assign(n, -1);
        lengths.clear(); parents.clear(); branches.clear();
        parentnodes.assign(n, -1); depths.assign(n, -1);

        sortednodes.clear(); offsets.clear();
        lefts.assign(n, -1); rights.assign(n, -1);

        vector<int> subtreesizes;
        measure(g, root, subtreesizes);

        typedef BuildDFSState State;
        depths[root] = 0;
        vector<State> s;
        s.push_back(State(root, 0, -1));
        while(!s.empty()) {
            State t = s.back(); s.pop_back();
            int i = t.i, len = t.len;
            int index = sortednodes.size();
            int color = lengths.size();

            if(t.parent == -3) {
                rights[i] = index;
                continue;
            }

            if(t.parent != -2) {
                assert(parents.size() == color);
                parents.push_back(t.parent);
                branches.push_back(len);
                offsets.push_back(index);
                len = 0;
            }
            colors[i] = color;
            positions[i] = len;

            lefts[i] = index;
            sortednodes.push_back(i);

            int maxsize = -1, maxj = -1;
            each(j, g[i]) if(colors[*j] == -1) {
                if(maxsize < subtreesizes[*j]) {
                    maxsize = subtreesizes[*j];
                    maxj = *j;
                }
                parentnodes[*j] = i;
                depths[*j] = depths[i] + 1;
            }
            s.push_back(State(i, -1, -3));
            if(maxj == -1) {
                lengths.push_back(len + 1);
            }else {
                each(j, g[i]) if(colors[*j] == -1 && *j != maxj)
                    s.push_back(State(*j, len, color));
                s.push_back(State(maxj, len + 1, -2));
            }
        }
    }
    
    void get(int v, int &c, int &p) const {
        c = colors[v]; p = positions[v];
    }
    bool go_up(int &c, int &p) const {
        p = branches[c]; c = parents[c];
        return c != -1;
    }

    inline const int *nodesBegin(int c) const { return &sortednodes[0] + offsets[c]; }
    inline const int *nodesEnd(int c) const { return &sortednodes[0] + offsets[c+1]; }

private:
    void measure(const vector<vi> &g, int root, vector<int> &out_subtreesizes) const {
        out_subtreesizes.assign(g.size(), -1);
        vector<int> s;
        s.push_back(root);
        while(!s.empty()) {
            int i = s.back(); s.pop_back();
            if(out_subtreesizes[i] == -2) {
                int s = 1;
                each(j, g[i]) if(out_subtreesizes[*j] != -2)
                    s += out_subtreesizes[*j];
                out_subtreesizes[i] = s;
            }else {
                s.push_back(i);
                each(j, g[i]) if(out_subtreesizes[*j] == -1)
                    s.push_back(*j);
                out_subtreesizes[i] = -2;
            }
        }
    }
};

int lowest_common_ancestor(const CentroidPathDecomposition &cpd, int x, int y) {
    int cx, px, cy, py;
    cpd.get(x, cx, px);
    cpd.get(y, cy, py);
    while(cx != cy) {
        if(cpd.depths[*cpd.nodesBegin(cx)] < cpd.depths[*cpd.nodesBegin(cy)])
            cpd.go_up(cy, py);
        else
            cpd.go_up(cx, px);
    }
    return cpd.nodesBegin(cx)[min(px, py)];
}


int main() {
    int N;
    scanf("%d", &N);
    vector<Val> initval(N);
    rep(i, N) {
        int a, b;
        scanf("%d%d", &a, &b);
        initval[i] = LinearExpr(a, b);
    }
    vector<vi> g(N);
    rep(i, N-1) {
        int x, y;
        scanf("%d%d", &x, &y), -- x, -- y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    CentroidPathDecomposition cpd;
    cpd.build(g, 0);
    vector<Val> permutatedInitval(N);
    rep(i, N)
        permutatedInitval[i] = initval[cpd.sortednodes[i]];
    SegmentTree segt;
    segt.init(permutatedInitval);
    vector<pii> path;
    int Q;
    scanf("%d", &Q);
    rep(ii, Q) {
        int ty;
        scanf("%d", &ty);
        if(ty == 1) {
            int u, v, a, b;
            scanf("%d%d%d%d", &u, &v, &a, &b), -- u, -- v;
            Laziness laziness(LinearExpr(a, b));
            int w = lowest_common_ancestor(cpd, u, v), wc, wp;
            cpd.get(w, wc, wp);
            rep(uv, 2) {
                int c, p;
                cpd.get(uv == 0 ? u : v, c, p);
                while(1) {
                    int top = c == wc ? wp + uv : 0;
                    int o = cpd.offsets[c], len = cpd.lengths[c];
                    //???[o + top, o + p]????? (????)
                    segt.addToRange(o + top, o + p + 1, laziness);
                    if(c == wc) break;
                    cpd.go_up(c, p);
                }
            }
        }else if(ty == 2) {
            int u, v, x;
            scanf("%d%d%d", &u, &v, &x), -- u, -- v;
            LinearExpr expr;
            int w = lowest_common_ancestor(cpd, u, v), wc, wp;
            cpd.get(w, wc, wp);
            rep(uv, 2) {
                path.clear();
                int c, p;
                cpd.get(uv == 0 ? u : v, c, p);
                while(1) {
                    int top = c == wc ? wp + uv : 0;
                    int o = cpd.offsets[c], len = cpd.lengths[c];
                    //???[o + top, o + p]????? (????)
                    path.push_back(mp(o + top, o + p));
                    if(c == wc) break;
                    cpd.go_up(c, p);
                }
                if(uv == 0) {
                    for(int i = 0; i < (int)path.size(); ++ i) {
                        int top = path[i].first, bottom = path[i].second;
                        expr += segt.getRange(top, bottom + 1).backward;
                    }
                }else {
                    for(int i = (int)path.size() - 1; i >= 0; -- i) {
                        int top = path[i].first, bottom = path[i].second;
                        expr += segt.getRange(top, bottom + 1).forward;
                    }
                }
            }
            mint ans = expr.evalute(x);
            printf("%d\n", ans.get());
        }else return 1;
    }
    return 0;
}


Problem solution in C programming.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _lnode{
  int x;
  int w;
  struct _lnode *next;
} lnode;
typedef struct _tree{
  long long sum[2][2];
  long long sum1[2][2];
  long long offset1;
  long long offset2;
} tree;
#define MOD 1000000007
void insert_edge(int x,int y,int w);
void dfs0(int u);
void dfs1(int u,int c);
void preprocess();
int lca(int a,int b);
void sum(int v,int tl,int tr,int l,int r,tree *t,long long ans[][2],int f);
void range_update(int v,int tl,int tr,int pos1,int pos2,long long o1,long long o2,tree *t);
void merge(long long a[][2],long long b[][2],long long ans[][2]);
void push(int v,int tl,int tr,tree *t);
void range_solve(int x,int y,int a,int b);
int min(int x,int y);
int max(int x,int y);
long long solve(int x,int y,int a);
void one(long long*a,int SIZE);
void mul(long long*a,long long*b,int SIZE);
void powm(long long*a,int n,long long*res,int SIZE);
int N,cn,A[100000],B[100000],level[100000],DP[18][100000],subtree_size[100000],special[100000],node_chain[100000],node_idx[100000],chain_head[100000],chain_len[100000]={0};
lnode *table[100000]={0};
tree *chain[100000];

int main(){
  int Q,x,y,a,b,i;
  scanf("%d",&N);
  for(i=0;i<N;i++)
    scanf("%d%d",A+i,B+i);
  for(i=0;i<N-1;i++){
    scanf("%d%d",&x,&y);
    insert_edge(x-1,y-1,1);
  }
  preprocess();
  scanf("%d",&Q);
  while(Q--){
    scanf("%d",&x);
    switch(x){
      case 1:
        scanf("%d%d%d%d",&x,&y,&a,&b);
        range_solve(x-1,y-1,a,b);
        break;
      default:
        scanf("%d%d%d",&x,&y,&a);
        printf("%lld\n",solve(x-1,y-1,a));
    }
  }
  return 0;
}
void insert_edge(int x,int y,int w){
  lnode *t=malloc(sizeof(lnode));
  t->x=y;
  t->w=w;
  t->next=table[x];
  table[x]=t;
  t=malloc(sizeof(lnode));
  t->x=x;
  t->w=w;
  t->next=table[y];
  table[y]=t;
  return;
}
void dfs0(int u){
  lnode *x;
  subtree_size[u]=1;
  special[u]=-1;
  for(x=table[u];x;x=x->next)
    if(x->x!=DP[0][u]){
      DP[0][x->x]=u;
      level[x->x]=level[u]+1;
      dfs0(x->x);
      subtree_size[u]+=subtree_size[x->x];
      if(special[u]==-1 || subtree_size[x->x]>subtree_size[special[u]])
        special[u]=x->x;
    }
  return;
}
void dfs1(int u,int c){
  lnode *x;
  node_chain[u]=c;
  node_idx[u]=chain_len[c]++;
  for(x=table[u];x;x=x->next)
    if(x->x!=DP[0][u])
      if(x->x==special[u])
        dfs1(x->x,c);
      else{
        chain_head[cn]=x->x;
        dfs1(x->x,cn++);
      }
  return;
}
void preprocess(){
  int i,j;
  level[0]=0;
  DP[0][0]=0;
  dfs0(0);
  for(i=1;i<18;i++)
    for(j=0;j<N;j++)
      DP[i][j] = DP[i-1][DP[i-1][j]];
  cn=1;
  chain_head[0]=0;
  dfs1(0,0);
  for(i=0;i<cn;i++){
    chain[i]=(tree*)malloc(4*chain_len[i]*sizeof(tree));
    memset(chain[i],0,4*chain_len[i]*sizeof(tree));
    for(j=0;j<4*chain_len[i];j++)
      chain[i][j].offset1=chain[i][j].offset2=-1;
  }
  for(i=0;i<N;i++)
    range_update(1,0,chain_len[node_chain[i]]-1,node_idx[i],node_idx[i],A[i],B[i],chain[node_chain[i]]);
  return;
}
int lca(int a,int b){
  int i;
  if(level[a]>level[b]){
    i=a;
    a=b;
    b=i;
  }
  int d = level[b]-level[a];
  for(i=0;i<18;i++)
    if(d&(1<<i))
      b=DP[i][b];
  if(a==b)return a;
  for(i=17;i>=0;i--)
    if(DP[i][a]!=DP[i][b])
      a=DP[i][a],b=DP[i][b];
  return DP[0][a];
}
void sum(int v,int tl,int tr,int l,int r,tree *t,long long ans[][2],int f){
  long long a[2][2],b[2][2];
  push(v,tl,tr,t);
  if(l>r){
    ans[0][0]=1;
    ans[0][1]=0;
    ans[1][0]=0;
    ans[1][1]=1;
    return;
  }
  if(l==tl && r==tr){
    if(f)
      memcpy(ans,t[v].sum1,sizeof(t[v].sum1));
    else
      memcpy(ans,t[v].sum,sizeof(t[v].sum));
    return;
  }
  int tm=(tl+tr)/2;
  sum(v*2,tl,tm,l,min(r,tm),t,a,f);
  sum(v*2+1,tm+1,tr,max(l,tm+1),r,t,b,f);
  if(f)
    merge(b,a,ans);
  else
    merge(a,b,ans);
  return;
}
void range_update(int v,int tl,int tr,int pos1,int pos2,long long o1,long long o2,tree *t){
  push(v,tl,tr,t);
  if(pos2<tl || pos1>tr)
    return;
  int tm=(tl+tr)/2;
  if(pos1<=tl && pos2>=tr){
    t[v].offset1=o1;
    t[v].offset2=o2;
  }
  else{
    range_update(v*2,tl,tm,pos1,pos2,o1,o2,t);
    range_update(v*2+1,tm+1,tr,pos1,pos2,o1,o2,t);
    push(v*2,tl,tm,t);
    push(v*2+1,tm+1,tr,t);
    merge(t[v*2].sum,t[v*2+1].sum,t[v].sum);
    merge(t[v*2+1].sum1,t[v*2].sum1,t[v].sum1);
  }
  return;
}
void merge(long long a[][2],long long b[][2],long long ans[][2]){
  ans[0][0]=(a[0][0]*b[0][0]+a[0][1]*b[1][0])%MOD;
  ans[0][1]=(a[0][0]*b[0][1]+a[0][1]*b[1][1])%MOD;
  ans[1][0]=(a[1][0]*b[0][0]+a[1][1]*b[1][0])%MOD;
  ans[1][1]=(a[1][0]*b[0][1]+a[1][1]*b[1][1])%MOD;
  return;
}
void push(int v,int tl,int tr,tree *t){
  long long a[2][2];
  if(t[v].offset1==-1 || t[v].offset2==-1)
    return;
  a[0][0]=t[v].offset1;
  a[0][1]=t[v].offset2;
  a[1][0]=0;
  a[1][1]=1;
  powm(&a[0][0],tr-tl+1,&t[v].sum[0][0],2);
  memcpy(t[v].sum1,t[v].sum,sizeof(t[v].sum));
  if(tl!=tr){
    t[v*2].offset1=t[v*2+1].offset1=t[v].offset1;
    t[v*2].offset2=t[v*2+1].offset2=t[v].offset2;
  }
  t[v].offset1=t[v].offset2=-1;
  return;
}
void range_solve(int x,int y,int a,int b){
  int ca=lca(x,y);
  while(node_chain[x]!=node_chain[ca]){
    range_update(1,0,chain_len[node_chain[x]]-1,0,node_idx[x],a,b,chain[node_chain[x]]);
    x=DP[0][chain_head[node_chain[x]]];
  }
  range_update(1,0,chain_len[node_chain[x]]-1,node_idx[ca],node_idx[x],a,b,chain[node_chain[x]]);
  while(node_chain[y]!=node_chain[ca]){
    range_update(1,0,chain_len[node_chain[y]]-1,0,node_idx[y],a,b,chain[node_chain[y]]);
    y=DP[0][chain_head[node_chain[y]]];
  }
  if(node_idx[y]!=node_idx[ca])
    range_update(1,0,chain_len[node_chain[y]]-1,node_idx[ca]+1,node_idx[y],a,b,chain[node_chain[y]]);
  return;
}
int min(int x,int y){
  return (x<y)?x:y;
}
int max(int x,int y){
  return (x>y)?x:y;
}
long long solve(int x,int y,int a){
  int ca=lca(x,y);
  long long t1[2][2],t2[2][2]={1,0,0,1},t3[2][2],ans[2][2];
  while(node_chain[x]!=node_chain[ca]){
    sum(1,0,chain_len[node_chain[x]]-1,0,node_idx[x],chain[node_chain[x]],t1,0);
    memcpy(t3,t2,sizeof(t2));
    merge(t1,t3,t2);
    x=DP[0][chain_head[node_chain[x]]];
  }
  sum(1,0,chain_len[node_chain[x]]-1,node_idx[ca],node_idx[x],chain[node_chain[x]],t1,0);
  memcpy(t3,t2,sizeof(t2));
  merge(t1,t3,ans);
  t2[0][0]=1;
  t2[0][1]=0;
  t2[1][0]=0;
  t2[1][1]=1;
  while(node_chain[y]!=node_chain[ca]){
    sum(1,0,chain_len[node_chain[y]]-1,0,node_idx[y],chain[node_chain[y]],t1,1);
    memcpy(t3,t2,sizeof(t2));
    merge(t3,t1,t2);
    y=DP[0][chain_head[node_chain[y]]];
  }
  if(node_idx[y]!=node_idx[ca]){
    sum(1,0,chain_len[node_chain[y]]-1,node_idx[ca]+1,node_idx[y],chain[node_chain[y]],t1,1);
    memcpy(t3,t2,sizeof(t2));
    merge(t3,t1,t2);
  }
  merge(t2,ans,t1);
  return (a*t1[0][0]+t1[0][1])%MOD;
}
void one(long long*a,int SIZE){
    int i,j;
    for (i = 0; i < SIZE; i++)
        for (j = 0; j < SIZE; j++)
            a[i*SIZE+j] = (i == j);
    return;
}
void mul(long long*a,long long*b,int SIZE){
    int i,j,k;
    long long res[SIZE][SIZE];
    for(i=0;i<SIZE;i++)
      for(j=0;j<SIZE;j++)
        res[i][j]=0;
    for (i = 0; i < SIZE; i++)
        for (j = 0; j < SIZE; j++)
            for (k = 0; k < SIZE; k++)
                res[i][j] = (res[i][j]+a[i*SIZE+k] * b[k*SIZE+j])%MOD;
    for (i = 0; i < SIZE; i++)
        for (j = 0; j < SIZE; j++)
            a[i*SIZE+j] = res[i][j];
    return;
}
void powm(long long*a,int n,long long*res,int SIZE){
    one(res,SIZE);
    while (n > 0) {
        if (n % 2 == 0)
        {
            mul(a, a,SIZE);
            n /= 2;
        }
        else {
            mul(res, a,SIZE);
            n--;
        }
    }
}