Header Ad

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

HackerRank Rooted Tree problem solution


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("%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;
}


Post a Comment

0 Comments