# HackerRank Rooted Tree problem solution

In this HackerRank Rooted Tree Problem solution you are given a rooted tree with N nodes and the root of the tree, R, is also given. Each node of the tree contains a value, that is initially empty. You have to maintain the tree under two operations:

1. Update Operation
2. Report Operation

## Problem solution in Java Programming.

```import java.io.*;
import java.util.*;

public class Solution {

static final int D = 17;
static final int MOD = 1_000_000_007;
static List<Integer>[] e;
static int[][] par;
static int[][] fenwick;
static int[] dep;
static int[] dfnl;
static int[] dfnr;
static int tick = 0;

static int lowestCommonAncestor(int u, int v) {
if (dep[u] < dep[v]) {
int temp = u;
u = v;
v = temp;
}
for (int i = D; --i >= 0; ) {
if (dep[u]-(1<<i) >= dep[v]) {
u = par[i][u];
}
}
if (u == v) {
return u;
}
for (int i = D; --i >= 0; ) {
if (par[i][u] != par[i][v]) {
u = par[i][u];
v = par[i][v];
}
}
return par[0][u];
}

static class Node {
int u;
int p;
boolean start = true;
Node(int u, int p) {
this.u = u;
this.p = p;
}
}

static void dfs(int u, int p) {
Deque<Node> queue = new LinkedList<>();
while (!queue.isEmpty()) {
Node node = queue.peek();
if (node.start) {
dfnl[node.u] = tick++;
for (int v: e[node.u]) {
if (v != node.p) {
par[0][v] = node.u;
dep[v] = dep[node.u]+1;
}
}
node.start = false;
} else {
dfnr[node.u] = tick;
queue.remove();
}
}
}

static void add(int fenwick[], int x, int v) {
for (; x < fenwick.length; x |= x+1) {
fenwick[x] = (fenwick[x] + v) % MOD;
}
}

static int getSum(int fenwick[], int x) {
int s = 0;
for (; x > 0; x &= x-1)
s = (s + fenwick[x-1]) % MOD;
return s;
}

static int get(int u) {
long pw = 1;
long s = 0;
for (int i = 0; i < 3; i++) {
s = (s + pw * getSum(fenwick[i], dfnl[u]+1)) % MOD;
pw = (pw * dep[u]) % MOD;
}
return (int) (((MOD+1l) / 2 * s)%MOD);
}

static int query(int u, int v) {
int w = lowestCommonAncestor(u, v);
long s = ((long)(get(u))+get(v)-get(w))%MOD;
if (par[0][w] >= 0) {
s = (s - get(par[0][w])) % MOD;
}
return (int) s;
}

static void upd(int fenwick[], int l, int r, int v) {
}

static void update(int u, int x, int y) {
int l = dfnl[u];
int r = dfnr[u];
upd(fenwick[2], l, r, y);
upd(fenwick[1], l, r, (int)(((long)(1 - 2 * dep[u]) * y + 2l * x) % MOD));
upd(fenwick[0], l, r, (int)((dep[u] * (dep[u] - 1l) * y + 2 * (1l - dep[u]) * x) % MOD));
}

public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int rt = Integer.parseInt(st.nextToken())-1;

e = new List[n];
for (int i = 0; i < n; i++) {
e[i] = new LinkedList<>();
}
for (int i = 0; i < n-1; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken())-1;
int v = Integer.parseInt(st.nextToken())-1;
}

dep = new int[n];
par = new int[D][n];
dfnl = new int[n];
dfnr = new int[n];

tick = 0;
dep[rt] = 0;
par[0][rt] = -1;
dfs(rt, -1);

for (int k = 1; k < D; k++) {
for (int i = 0; i < n; i++) {
par[k][i] = par[k-1][i] == -1 ? par[k-1][i] : par[k-1][par[k-1][i]];
}
}

fenwick = new int[3][n];

while (m-- > 0) {
st = new StringTokenizer(br.readLine());
char op = st.nextToken().charAt(0);
int u = Integer.parseInt(st.nextToken()) - 1;
int v = Integer.parseInt(st.nextToken());
if (op == 'Q') {
v--;
int result = (query(u, v)+MOD)%MOD;
bw.write(result + "\n");
} else {
int w = Integer.parseInt(st.nextToken());
update(u, v, w);
}
}

bw.newLine();
bw.close();
br.close();
}
}```

## 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>
#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; }

struct To {
typedef int Vertex;
Vertex to;
To() { }
To(Vertex to_): to(to_) { }
};

template<typename To_>
struct StaticGraph {
typedef To_ To;
typedef typename To::Vertex Vertex;
typedef std::pair<Vertex,To> Edge;
typedef const To *const_iterator;

void init(int n_, const std::vector<Edge> &edges) {
n = n_; int m = edges.size();
tos.resize(m+1); offsets.resize(n+1);
for(int e = 0; e < m; e ++) offsets[edges[e].first] ++;
for(int v = 1; v <= n_; v ++) offsets[v] += offsets[v-1];
for(int e = 0; e < m; e ++)
tos[-- offsets[edges[e].first]] = edges[e].second;
}
int numVertices() const { return n; }
int numEdges() const { return tos.size() - 1; }

inline const_iterator edgesBegin(int v) const { return &tos[offsets[v]]; }
inline const_iterator edgesEnd(int v) const { return &tos[offsets[v+1]]; }
private:
int n;
std::vector<To> tos;
std::vector<int> offsets;
};

class SchieberVishkinLCA {
public:
typedef StaticGraph<To> Graph;
typedef unsigned Word;
typedef Graph::Vertex Vertex;
private:

static inline Word lowestOneBit(Word v) {
return v & (~v+1);
}
static inline Word highestOneBitMask(Word v) {
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
return v >> 1;
}

std::vector<Word> indices;            //Vertex -> index
std::vector<Word> maxHIndices;        //Vertex -> index
std::vector<Word> ancestorHeights;    //Vertex -> Word
std::vector<Vertex> pathParents;    //index-1 -> Vertex
public:
//g?????????????
void build(const Graph &g, Vertex root) {
return build(g, std::vector<Vertex>(1, root));
}
void build(const Graph &g, const std::vector<Vertex> &roots) {
int N = g.numVertices();

ancestorHeights.resize(N);
std::vector<Vertex> parents(N);
maxHIndices.resize(N);
std::vector<Vertex> vertices; vertices.reserve(N);
indices.resize(N);

//inorder traversal
Word currentIndex = 1;
for(int ri = 0; ri < (int)roots.size(); ri ++) {
Vertex root = roots[ri];
parents[root] = root;    //???????
vertices.push_back(root);
}
while(!vertices.empty()) {
Vertex v = vertices.back(); vertices.pop_back();
indices[v] = currentIndex ++;
for(const Graph::To *it = g.edgesBegin(v); it != g.edgesEnd(v); ++ it) {
parents[it->to] = v;
vertices.push_back(it->to);
}
}

//BFS (???????????????)
int head = 0, tail = roots.size();
vertices.resize(N);
for(int ri = 0; ri < (int)roots.size(); ri ++)
vertices[ri] = roots[ri];
while(head != tail) {
Vertex v = vertices[head ++];
for(const Graph::To *it = g.edgesBegin(v); it != g.edgesEnd(v); ++ it)
vertices[tail ++] = it->to;
}

//?????
for(std::vector<Vertex>::const_iterator it = vertices.begin(); it != vertices.end(); ++ it)
maxHIndices[*it] = indices[*it];
for(std::vector<Vertex>::const_reverse_iterator it = vertices.rbegin(); it != vertices.rend(); ++ it) {
Vertex v = *it, parent = parents[v];
if(lowestOneBit(maxHIndices[parent]) < lowestOneBit(maxHIndices[v]))
maxHIndices[parent] = maxHIndices[v];
}

//A????
for(int ri = 0; ri < (int)roots.size(); ri ++) {
Vertex root = roots[ri];
ancestorHeights[root] = 0;
}
for(std::vector<Vertex>::const_iterator it = vertices.begin(); it != vertices.end(); ++ it) {
Vertex v = *it;
ancestorHeights[v] = ancestorHeights[parents[v]] | lowestOneBit(maxHIndices[v]);
}

pathParents.swap(parents);    //???????
for(int ri = 0; ri < (int)roots.size(); ri ++) {
Vertex root = roots[ri];
pathParents[indices[root]-1] = root;
}
for(std::vector<Vertex>::const_iterator it = vertices.begin(); it != vertices.end(); ++ it) {
Vertex v = *it;
for(const Graph::To *jt = g.edgesBegin(v); jt != g.edgesEnd(v); ++ jt) {
if(maxHIndices[v] != maxHIndices[jt->to])
pathParents[indices[jt->to]-1] = v;
else
pathParents[indices[jt->to]-1] = pathParents[indices[v]-1];
}
}
}

Vertex query(Vertex v, Vertex u) const {
//binary tree???LCA???????
Word Iv = maxHIndices[v], Iu = maxHIndices[u];
Word hIv = lowestOneBit(Iv), hIu = lowestOneBit(Iu);
Word hbMask = highestOneBitMask((Iv ^ Iu) | hIv | hIu);
Word j = lowestOneBit(ancestorHeights[v] & ancestorHeights[u] & ~hbMask);
//j = hI(lca(v,u)) ??? (????hI(x) = 2^(complete binary tree???I(x)???), I(x) = maxHIndices[x])
//(hI(lca(v,u)) = j)?hI(v)?hI(u)????????????????????????…
Vertex x, y;
if(j == hIv) x = v;
else {            //lca?v????????
Word kMask = highestOneBitMask(ancestorHeights[v] & (j-1));    //v?????j???????????????????
x = pathParents[(indices[v] & ~kMask | (kMask+1))-1];    //indices[v]?k???????????
}
if(j == hIu) y = u;
else {            //lca?u????????
Word kMask = highestOneBitMask(ancestorHeights[u] & (j-1));    //u?????j???????????????????
y = pathParents[(indices[u] & ~kMask | (kMask+1))-1];    //indices[u]?k???????????
}
return indices[x] < indices[y] ? x : y;    //in-order????????????????????
}
};

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; }
ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
typedef ModInt<1000000007> mint;

struct Val {
bool sign; mint x; int depth;
Val() { }
Val(bool sign_, mint x_, int depth_): sign(sign_), x(x_), depth(depth_) { }
};

struct Sum {
mint signedSum, signedDepthSum, signedCount;
Sum(): signedSum(0), signedDepthSum(0), signedCount(0) { }
Sum(const Val &val, int pos) {
bool sign = val.sign;
signedDepthSum = !sign ? val.depth : -val.depth;
signedSum = !sign ? val.x : -val.x;
signedCount = !sign ? 1 : -1;
}
Sum &operator+=(const Sum &that) {
signedSum += that.signedSum;
signedDepthSum += that.signedDepthSum;
signedCount += that.signedCount;
return *this;
}
Sum operator+(const Sum &that) const { return Sum(*this) += that; }
};

struct Laziness {
Laziness &operator+=(const Laziness &that) {
return *this;
}
void addToVal(Val &val, int pos_) const {
val.x += add0 + add1 * val.depth;
}
void addToSum(Sum &sum, int left_, int right_) const {
sum.signedSum += add0 * sum.signedCount + add1 * sum.signedDepthSum;
}
};

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 = 2; 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) {
static int indices[128];
int k = getIndices(indices, i, i+1);
propagateRange(indices, k);
return leafs[i];
}
Sum getRange(int i, int j) {
static 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;
}
void set(int i, const Val &x) {
static 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;
static 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[128], int i, int j) {
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;
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);
laziness[i].addToVal(leafs[i * 2 + 1 - n], i * 2 + 1);
}
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);
}
};

vector<int> t_parent;
vi t_seq; vector<bool> t_sign;
vector<int> t_left, t_right;

void tree_signedeulertour(const vector<vi> &g, int root) {
int n = g.size();
t_parent.assign(n, -1);
t_left.assign(n, -1);
t_right.assign(n, -1);
t_seq.assign(n * 2, -1);
t_sign.assign(n * 2, false);
int pos = 0;

vector<int> stk; stk.push_back(root);
while(!stk.empty()) {
int i = stk.back(); stk.pop_back();
if(i < 0) {
i = -i - 1;
t_seq[pos] = i;
t_sign[pos] = true;
pos ++;
t_right[i] = pos;
continue;
}
t_left[i] = pos;
t_seq[pos] = i;
t_sign[pos] = false;
pos ++;

stk.push_back(-(i+1));
for(int j = (int)g[i].size()-1; j >= 0; j --) {
int c = g[i][j];
if(t_parent[c] == -1 && c != root)
stk.push_back(c);
else
t_parent[i] = c;
}
}
}

int main() {
int N, Q, root;
scanf("%d%d%d", &N, &Q, &root), root --;
vector<vi> g(N);
rep(i, N-1) {
int a, b;
scanf("%d%d", &a, &b), a --, b --;
g[a].pb(b);
g[b].pb(a);
}
tree_signedeulertour(g, root);
vi depth(N, -1);
rep(ix, t_seq.size()) if(!t_sign[ix]) {
int i = t_seq[ix];
depth[i] = i == root ? 0 : depth[t_parent[i]] + 1;
}

vector<SchieberVishkinLCA::Graph::Edge> edges;
rep(i, N) if(i != root) {
edges.push_back(SchieberVishkinLCA::Graph::Edge(t_parent[i], i));
}
SchieberVishkinLCA lca;
SchieberVishkinLCA::Graph gg; gg.init(N, edges);
lca.build(gg, root);

SegmentTree segt;
{    vector<Val> vals;
rep(i, t_seq.size())
vals.push_back(Val(t_sign[i], 0, depth[t_seq[i]]));
segt.init(vals);
}
rep(ii, Q) {
static char q[2];
scanf("%s", q);
if(*q == 'U') {
int T, V, K;
scanf("%d%d%d", &T, &V, &K), T --;
Laziness l(mint(V) - mint(K) * depth[T], K);
}else {
int A, B;
scanf("%d%d", &A, &B), A --, B --;
int C = lca.query(A, B);
mint ans = 0;
ans += segt.getRange(t_left[C], t_left[A]+1).signedSum;
ans += segt.getRange(t_left[C]+1, t_left[B]+1).signedSum;
printf("%d\n", ans.get());
}
}
return 0;
}```

## Problem solution in C programming.

```#include <stdio.h>
#include <string.h>
#define prime 1000000007L
#define uprime 1000000007U
#define ulprime 1000000007UL

static inline long mod(long self) {
return (self % prime) + ((self >> 63) & prime);
}

void descending_order(unsigned *self, unsigned *weights, unsigned length) {
unsigned
at,
root = length >> 1,
member;

for (self--; root; self[at >> 1] = member) {
member = self[root];

for (at = root-- << 1; at <= length; at <<= 1) {
at |= (at < length) && weights[self[at | 1]] < weights[self[at]];
if (weights[member] <= weights[self[at]])
break ;

self[at >> 1] = self[at];
}
}

for (; length > 1; self[at >> 1] = member) {
member = self[length];
self[length--] = self[1];

for (at = 2; at <= length; at <<= 1) {
at |= (at < length) && (weights[self[at | 1]] < weights[self[at]]);
if (weights[member] <= weights[self[at]])
break ;

self[at >> 1] = self[at];
}
}
}

long point_query(
unsigned vertex_cnt,
unsigned sums[vertex_cnt][3],
int *depths,
unsigned at
) {
unsigned
totals[3] = {0, 0, 0},
node = at;

for (; node < vertex_cnt; node = (node & (node + 1U)) - 1U) {
((unsigned long *)totals)[0] += ((unsigned long *)(sums[node]))[0];
totals[0] %= uprime;
totals[1] %= uprime;
totals[2] = (totals[2] + sums[node][2]) % uprime;
}

long total = ((unsigned long)depths[(long)(int)at] * depths[(long)(int)at] * totals[0]) % ulprime;
total = (total + ((unsigned long)depths[(long)(int)at] * totals[1])) % ulprime;

return (mod(total - (long)totals[2]) * 500000004UL) % ulprime;
}

int main() {
unsigned vertex_cnt, operation_cnt, root;
scanf("%u %u %u", &vertex_cnt, &operation_cnt, &root);

unsigned
at = vertex_cnt,
others,
ancestors[vertex_cnt];
{
unsigned next, ancestor, descendant;
for (memset(ancestors, 0xFFU, sizeof(ancestors)); --at; ancestors[descendant] = ancestor) {
scanf("%u %u", &ancestor, &descendant);

--ancestor;
if (ancestors[--descendant] != 0xFFFFFFFFU) {
ancestor   ^= descendant;
descendant ^= ancestor;
ancestor   ^= descendant;
}
if (ancestors[descendant] != 0xFFFFFFFFU) {
for (others = descendant; ancestor != 0xFFFFFFFFU; ancestor = next) {
next = ancestors[ancestor];
ancestors[ancestor] = others;
others = ancestor;
}
for (; ancestors[descendant] != 0xFFFFFFFFU; ancestor = next) {
next = ancestors[descendant];
ancestors[descendant] = ancestor;
ancestor = descendant;
}
}
}
ancestor = 0xFFFFFFFFU;
for (at = --root; at != 0xFFFFFFFFU; at = next) {
next = ancestors[at];
ancestors[at] = ancestor;
ancestor = at;
}
}

unsigned
weights[vertex_cnt],
ids[vertex_cnt],
bases[vertex_cnt],
base_cnt = 1;
{
unsigned
indices[vertex_cnt + 1],
descendants[vertex_cnt - 1];

ancestors[root] = root;
memset(indices, 0, sizeof(indices));
for (at = vertex_cnt; at--; indices[ancestors[at]]++);
for (indices[root]--; ++at < vertex_cnt; indices[at + 1] += indices[at]);
for (indices[at] = at - 1; --at > root; descendants[--indices[ancestors[at]]] = at);
for (; at--; descendants[--indices[ancestors[at]]] = at);

unsigned history[vertex_cnt];

memset(weights, 0, sizeof(weights));
history[0] = root;
for (at = 1; at--; )
if (weights[history[at]])
for (others = indices[history[at]];
others < indices[history[at] + 1];
weights[history[at]] += weights[descendants[others++]]);
else {
weights[history[at]] = 1;
memcpy(
&history[at + 1],
&descendants[indices[history[at]]],
sizeof(history[0]) * (indices[history[at] + 1] - indices[history[at]])
);
at += 1 + (indices[history[at] + 1] - indices[history[at]]);
}

unsigned orig_weights[vertex_cnt];
memcpy(orig_weights, weights, sizeof(weights));

bases[(ids[root] = 0)] = 0;
weights[0] = vertex_cnt;
for (at = 1; at--; ) {
others = history[at];
descending_order(
memcpy(
&history[at],
&descendants[indices[others]],
sizeof(history[0]) * (indices[others + 1] - indices[others])
),
orig_weights,
(indices[others + 1] - indices[others])
);

root = ids[others];
others = at + (indices[others + 1] - indices[others]);

unsigned
base = bases[root],
id = root + 1;

for (base_cnt += (others - at) - (at < others); at < others; base = (id += weights[id])) {
ids[history[at]] = id;

ancestors[id] = root;
bases[id] = base;
weights[id] = orig_weights[history[at++]];
}
}
}

int
buffers[vertex_cnt + 1],
*depths = &buffers[1];

ancestors[0] = 0;
for (((unsigned long *)buffers)[0] = 0; ++at < vertex_cnt; depths[at] = depths[ancestors[at]] + 1);

unsigned base_ids[vertex_cnt];
unsigned char
base_depths[base_cnt],
max_depth = 0;

base_depths[0] = 0;
for (base_ids[(at = 0)] = 0; ++at < vertex_cnt; ) {
base_ids[at] = base_ids[at - 1];

if (bases[at] != bases[at - 1]) {
base_depths[++base_ids[at]] = base_depths[base_ids[ancestors[bases[at]]]] + (unsigned char)1;

if (max_depth < base_depths[base_ids[at]])
max_depth = base_depths[base_ids[at]];
}
}

unsigned ancestral_bases[base_cnt][max_depth];
memset(ancestral_bases[0], 0, sizeof(ancestral_bases[0]));
for (at = 0; ++at < vertex_cnt; ancestral_bases[base_ids[at]][0] = ancestors[bases[at]]);

for (others = 0; (others + 1) < max_depth; others++)
for (at = 0; ++at < base_cnt; ancestral_bases[at][others + 1] = ancestors[bases[ancestral_bases[at][others]]]);

unsigned sums[vertex_cnt][3];
memset(sums, 0, sizeof(sums));

ancestors[0] = 0xFFFFFFFFU;
for (getchar(); operation_cnt--; getchar())
if (getchar() == 'U') {
scanf(" %u %u %u", &root, &at, &others);
root = ids[root - 1];

unsigned coefs[4] = {
[0] = others,
[1] = (unsigned) mod((long)(at << 1) - mod((long)others * ((depths[root] << 1) - 1L))),
[2] = (unsigned) mod((depths[root] - 1L) * mod((long)(at << 1) - mod((long)others * depths[root])))
};
for (at = root; at < (root + weights[root]); at |= at + 1U) {
((unsigned long *)(sums[at]))[0] += ((unsigned long *)coefs)[0];

sums[at][0] %= uprime;
sums[at][1] %= uprime;
sums[at][2] = (sums[at][2] + coefs[2]) % uprime;
}

((unsigned long *) coefs)[0] = ((ulprime << 32) | ulprime) - ((unsigned long *) coefs)[0];
((unsigned long *) coefs)[1] = ((ulprime << 32) | ulprime) - ((unsigned long *) coefs)[1];
coefs[0] %= uprime;
coefs[1] %= uprime;
coefs[2] %= uprime;

if (at > vertex_cnt)
at = vertex_cnt;

for (others = root + weights[root]; others < at; others |= others + 1U) {
((unsigned long *)(sums[others]))[0] += ((unsigned long *)coefs)[0];

sums[others][0] %= uprime;
sums[others][1] %= uprime;
sums[others][2] = (sums[others][2] + coefs[2]) % uprime;
}
} else {
scanf(" %u %u", &at, &others);
at = ids[at - 1];
others = ids[others - 1];

if (others < at) {
at ^= others;
others ^= at;
at ^= others;
}

if (others < (at + weights[at]))
root = at;
else {
unsigned *members = ancestral_bases[base_ids[others]];
unsigned char dist = base_depths[base_ids[others]];
for (; dist > 1; dist >>= 1)
if (members[dist >> 1] > at) {
members += (dist >> 1);
dist += dist & 1U;
}
root = members[members[0] > at];
}

printf(
"%lu\n",
(
mod(
point_query(vertex_cnt, sums, depths, at)
- point_query(vertex_cnt, sums, depths, root)
)
+ mod(
point_query(vertex_cnt, sums, depths, others)
- point_query(vertex_cnt, sums, depths, ancestors[root])
)
) % ulprime
);
}

return 0;
}```