using namespace std; typedef vector vi; typedef pair pii; typedef vector > vpii; typedef long long ll; typedef vector vl; typedef pair pll; typedef vector > vpll; typedef vector vs; typedef long double ld; template inline void amin(T &x, U y) { if(y < x) x = y; } template 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 struct StaticGraph { typedef To_ To; typedef typename To::Vertex Vertex; typedef std::pair 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 tos; std::vector offsets; };

class SchieberVishkinLCA { public: typedef StaticGraph 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(1, root)); } void build(const Graph &g, const std::vector &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 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 leafs; vector nodes; vector laziness; vector leftpos, rightpos; int n, n2; void init(int n_, const Val &v = Val()) { init(vector(n_, v)); } void init(const vector &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 t_parent; vi t_seq; vector t_sign; vector t_left, t_right;

void tree_signedeulertour(const vector &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 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;

}

Rust solution - work in progress here. The solution so far produces correct results, but has TLE's and is in need of some optimization. I'm looking at compressing the sparse branches while preserving the ability to calculate node values on the fly.

Things I wish the problem description had told me:

• The end points of the edges in the input data can be in either order.
• May need to traverse tree starting at root to fix parent child relationships.
• The queries can involve finding common ancestor.
• Update values with +=: .value += v + d * k;

include

include

include

include

include

using namespace std;

long Max = 1000000; long N; long Root;

struct Node { long long value = 0; long height = 0; vector childNoes; };

void DeLinkParentFromChild(long R, Node* arr, long P, long height) { Node* node = &arr[R]; node->height = height; int size = node->childNoes.size(); for(long i = 0; i < size; ++i) { long index = node->childNoes[i]; if(index > N) continue;

    if(index == P)
    {
        node->childNoes[i] += Max;
    }
    else
        DeLinkParentFromChild(index, arr, R, height+1);
}

}

void AddValue(Node* arr, long T, int K, long long value) { Node* node = &arr[T]; node->value += value;

long long nextValue = value + K;
int size = node->childNoes.size();
for(long i = 0; i < size;++i)
{
    long index = node->childNoes[i];
    if(index > N)
        continue;
    AddValue(arr, index, K, nextValue);
}

}

void GetSum(Node* arr, long A, long B, long long& sum, bool& bFound) { while (arr[A].height > arr[B].height) { Node* node = &arr[A]; sum += node->value;

    int size = node->childNoes.size();
    for (long i = 0; i < size; ++i)
    {
        long index = node->childNoes[i];
        if (index <= N)
            continue;
        A = index-Max;
        break;
    }
}

while (arr[A].height < arr[B].height)
{
    Node* node = &arr[B];
    sum += node->value;

    int size = node->childNoes.size();
    for (long i = 0; i < size; ++i)
    {
        long index = node->childNoes[i];
        if (index <= N)
            continue;
        B = index-Max;
        break;
    }
}

if (A == B)
{
    sum += arr[A].value;
    bFound = true;
    return;
}

while (arr[A].height > 0)
{
    Node* nodeA = &arr[A];
    sum += nodeA->value;
    int size = nodeA->childNoes.size();
    for (long i = 0; i < size; ++i)
    {
        long index = nodeA->childNoes[i];
        if (index <= N)
            continue;
        A = index-Max;
        break;
    }

    Node* nodeB = &arr[B];
    sum += nodeB->value;
    size = nodeB->childNoes.size();
    for (long i = 0; i < size; ++i)
    {
        long index = nodeB->childNoes[i];
        if (index <= N)
            continue;
        B = index-Max;
        break;
    }


    if (A == B)
    {
        sum += arr[A].value;
        bFound = true;
        return;
    }
}

}

int main() {
long E; long R;

cin>>N>>E>>R;
Root = R;

Node* arr = new Node[N+1];  

for(long i = 0; i < N-1;++i)
{
    long X, Y;
    cin>>X>>Y;
    arr[X].childNoes.push_back(Y);
    arr[Y].childNoes.push_back(X);
}  

DeLinkParentFromChild(R, arr, -1, 0);

for(long i = 0; i < E;++i)
{
   char ch;
   cin>>ch;
   if(ch == 'U')
   {           
       long T, V, K;
       cin>>T>>V>>K;
       AddValue(arr, T, K, V);
   }
   else if(ch == 'Q')
   {            
       long A, B;
       cin>>A>>B;

       long long sum = 0;
       bool bFound = false;
       GetSum(arr, A, B, sum, bFound);
       if(!bFound)
        sum = 0;
       cout<<sum%(1000000007)<<endl;
   }
}

return 0;

}

Solution in C++

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for(int i = a; i < b; i++)
#define S(x) scanf("%d",&x)
#define P(x) printf("%d\n",x)
typedef long long int LL;

const int mod = 1000000007;
const int MAXN = 100005;
vector<int> g[MAXN];
int dep[MAXN];
int P[MAXN];
int _tm;
int tin[2 * MAXN];
int tout[2 * MAXN];
int n;
int L[MAXN][25];
LL bit1[2 * MAXN], bit2[2 * MAXN], bit3[2 * MAXN];

LL _pow(LL a, LL b){
    if(!b) return 1;
    if(b == 1) return a;
    if(b == 2) return (a * a) % mod;
    if(b & 1) return (a * _pow(a, b - 1)) % mod;
    return _pow(_pow(a, b / 2), 2);
}

void dfs(int c, int p, int d){
    P[c] = p;
    dep[c] = d;
    _tm++;
    tin[c] = _tm;
    rep(i, 0, g[c].size()){
        int u = g[c][i];
        if(u != p) dfs(u, c, d + 1);
    }
    _tm++;
    tout[c] = _tm;
}

void processLca(){
    int i, j;
  //we initialize every element in P with -1
    int N = n;
      for(i = 0; i < n; i++)
          for(j = 0; 1 << j < N; j++)
              L[i][j] = -1; 
  //the first ancestor of every node i is T[i]
      for(i = 0; i < N; i++)
          L[i][0] = P[i];
  //bottom up dynamic programing
      for(j = 1; 1 << j < N; j++)
         for(i = 0; i < N; i++)
             if (L[i][j - 1] != -1)
                 L[i][j] = L[L[i][j - 1]][j - 1];
}

int lca(int p, int q){
      int tmp, log, i;
  //if p is situated on a higher level than q then we swap them
      if (dep[p] < dep[q])
          tmp = p, p = q, q = tmp;
  //we compute the value of [log(L[p)]
      for(log = 1; 1 << log <= dep[p]; log++);
      log--;
  //we find the ancestor of node p situated on the same level
  //with q using the values in P
      for(i = log; i >= 0; i--)
          if (dep[p] - (1 << i) >= dep[q])
              p = L[p][i];
      if (p == q)
          return p;
  //we compute LCA(p, q) using the values in P
      for(i = log; i >= 0; i--)
          if (L[p][i] != -1 && L[p][i] != L[q][i])
              p = L[p][i], q = L[q][i];
      return P[p];
}

void update(LL *bit, int idx, LL val){
    for(int i = idx; i <= _tm; i += i & -i) bit[i] += val;
}

LL query(LL *bit, int idx){
    LL res = 0;
    for(int i = idx; i; i -= i & -i){
        res += bit[i];
    }
    return res % mod;
}

LL QQQ(int x){
    LL res;
    LL c = dep[x];
    res = (query(bit1, tin[x]) * c) % mod;
    res += (query(bit2, tin[x]) * (((LL)c * c)%mod));
    res %= mod;
    res += query(bit3, tin[x]);
    return res % mod;
}

int main(){
    int e, r;
    scanf("%d%d%d", &n, &e, &r);
    r--;
    rep(i, 0, n - 1){
        int x, y;
        scanf("%d%d", &x, &y);
        x--; y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(r,-1,0);
    processLca();
    while(e--){
        char s[5];
        scanf("%s", s);
        if(s[0] == 'U'){
            int T, V, K;
            scanf("%d%d%d", &T, &V, &K);
            T--;
            LL k = ((LL)K * _pow(2, mod - 2)) % mod;
            LL p = dep[T];
            LL val;
            val = (V - 2 * p * k + k) % mod;
            val = (val + mod) % mod;
            update(bit1, tin[T], val);
            update(bit1, tout[T] + 1, -val);
            val = k;
            update(bit2, tin[T], val);
            update(bit2, tout[T] + 1, -val);
            val = (p * p) % mod;
            val = (val * k) % mod;
            val -= p * (V + k);
            val %= mod;
            val += mod + V;
            val %= mod;
            update(bit3, tin[T], val);
            update(bit3, tout[T] + 1, -val);
        } else {
            int A, B;
            scanf("%d%d", &A, &B);
            A--; B--;
            LL ans = 0;
            int l = lca(A, B);
            ans = QQQ(A) + QQQ(B) - QQQ(l);
            if(P[l] != -1) ans -= QQQ(P[l]);
            ans %= mod;
            ans += mod;
            ans %= mod;
            printf("%lld\n", ans);
        }
    }
    return 0;
}

I'm having difficulty understanding this editorial, which means I may not understand the question. I don't see how an update can be done in log n time. It seems like it would be more efficient to simply update the array, not the sums in a BIT.

Consider the array with positions 1-17. Using a BIT, updating index 4 would cause updates to 8 and 16. All of 4's descendants would have this same cost. Therefore the updates would take nlog n time, not log n. Using an array, updates would take n time (n being the nodes you need to update) because you're simply updating indexes. Note that for this post, I’m not counting the cost of finding the descendants of a node.

Any thoughts?