HackerRank Rooted Tree problem solution YASH PAL, 31 July 2024 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: Update Operation 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<>(); queue.add(new Node(u, p)); 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; queue.addFirst(new Node(v, node.u)); } } 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) { add(fenwick, l, v); add(fenwick, r, -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 { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 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; e[u].add(v); e[v].add(u); } 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 { mint add0, add1; Laziness(): add0(0), add1(0) { } Laziness(mint add0_, mint add1_): add0(add0_), add1(add1_) { } Laziness &operator+=(const Laziness &that) { add0 += that.add0; add1 += that.add1; 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; 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); 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); segt.addToRange(t_left[T], t_right[T], l); }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("%dn", 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( "%lun", ( 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; } coding problems data structure