In this HackerRank Fibonacci Numbers Tree problem we have given the configuration for the tree and a list of operations, perform all the operations efficiently.
Problem solution in Java Programming.
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class H {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
int n = ni();
int Q = ni();
par = new int[n];
for(int i = 1;i < n;i++){
par[i] = ni()-1;
}
par[0] = -1;
int[][] g = parentToG(par);
int[][] pars = parents3(g, 0);
int[] ord = pars[1], dep = pars[2];
clus = decomposeToHeavyLight(g,par, ord);
cluspath = clusPaths(clus, ord);
clusiind = clusIInd(cluspath, n);
int m = cluspath.length;
sts = new SegmentTreeMatrix[m];
for(int i = 0;i < m;i++){
sts[i] = new SegmentTreeMatrix(cluspath[i].length);
}
int[][] spar = logstepParents(par);
for(int z = 0;z < Q;z++){
char type = nc();
if(type == 'U'){
int x = ni()-1;
long K = nl();
sts[clus[x]].update(clusiind[x], K);
}else{
int mod = 1000000007;
int x = ni()-1, y = ni()-1;
int lca = lca2(x, y, spar, dep);
long ret = d(x)+d(y)-d(lca)-d(par[lca]);
ret %= mod;
if(ret < 0)ret += mod;
out.println(ret);
}
}
}
int[] par;
int[] clus, clusiind;
int[][] cluspath;
SegmentTreeMatrix[] sts;
long d(int x)
{
if(x == -1)return 0;
int[] lcx = new int[100];
int[] lto = new int[100];
int p = 0;
int cx = clus[x];
int ind = clusiind[x];
while (true) {
lcx[p] = cx;
lto[p] = ind+1;
p++;
int con = par[cluspath[cx][0]];
if(con == -1)break;
ind = clusiind[con];
cx = clus[con];
}
int[] v = {0, 0, 1, 0};
for(int i = p-1;i >= 0;i--){
v = sts[lcx[i]].apply(0, lto[i], v);
}
return v[3];
}
public static class SegmentTreeMatrix {
public int M, H, N;
public int[][][] node;
public static int mod = 1000000007;
public static long BIG = 8L*mod*mod;
public static int S = 4;
public SegmentTreeMatrix(int n)
{
N = n;
M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
H = M>>>1;
node = new int[M][][];
for(int i = 0;i < N;i++){
node[H+i] = new int[S][S];
node[H+i][0][0] = 1;
node[H+i][0][1] = 1;
node[H+i][1][0] = 1;
node[H+i][3][1] = 1;
node[H+i][2][2] = 1;
node[H+i][3][3] = 1;
node[H+i][3][0] = 1;
}
for(int i = H-1;i >= 1;i--)propagate(i);
}
private void propagate(int cur)
{
node[cur] = prop2(node[2*cur], node[2*cur+1], node[cur]);
}
private int[][] prop2(int[][] L, int[][] R, int[][] C)
{
if(L != null && R != null){
C = mul(R, L, C, mod);
return C;
}else if(L != null){
return prop1(L, C);
}else if(R != null){
return prop1(R, C);
}else{
return null;
}
}
private int[][] prop1(int[][] L, int[][] C)
{
if(C == null){
// C = L; // read only
C = new int[S][];
for(int i = 0;i < S;i++){
C[i] = Arrays.copyOf(L[i], S);
}
}else{
for(int i = 0;i < S;i++){
C[i] = Arrays.copyOf(L[i], S);
}
}
return C;
}
public void update(int pos, long x) {
int[][] M = {{1, 1}, {1, 0}};
int[] v = {1, 0};
v = pow(M, v, x-1);
node[H+pos][0][2] += v[0];
if(node[H+pos][0][2] >= mod)node[H+pos][0][2] -= mod;
node[H+pos][1][2] += v[1];
if(node[H+pos][1][2] >= mod)node[H+pos][1][2] -= mod;
node[H+pos][3][2] += v[0];
if(node[H+pos][3][2] >= mod)node[H+pos][3][2] -= mod;
for(int i = H+pos>>>1;i >= 1;i>>>=1)propagate(i);
}
public int[] apply(int l, int r, int[] v){
return apply(l, r, 0, H, 1, v);
}
protected int[] apply(int l, int r, int cl, int cr, int cur, int[] v)
{
if(l <= cl && cr <= r){
return mul(node[cur], v, mod);
}else{
int mid = cl+cr>>>1;
if(cl < r && l < mid){
v = apply(l, r, cl, mid, 2*cur, v);
}
if(mid < r && l < cr){
v = apply(l, r, mid, cr, 2*cur+1, v);
}
return v;
}
}
public static int[] mul(int[][] A, int[] v, int mod)
{
int m = A.length;
int n = v.length;
int[] w = new int[m];
for(int i = 0;i < m;i++){
long sum = 0;
for(int k = 0;k < n;k++){
sum += (long)A[i][k] * v[k];
if(sum >= BIG)sum -= BIG;
}
w[i] = (int)(sum % mod);
}
return w;
}
public static int[][] mul(int[][] A, int[][] B, int[][] C, int mod)
{
int m = A.length;
int n = A[0].length;
int o = B[0].length;
if(C == null)C = new int[m][o];
for(int i = 0;i < m;i++){
for(int j = 0;j < o;j++){
long sum = 0;
for(int k = 0;k < n;k++){
sum += (long)A[i][k] * B[k][j];
if(sum >= BIG)sum -= BIG;
}
sum %= mod;
C[i][j] = (int)sum;
}
}
return C;
}
// A^e*v
public static int[] pow(int[][] A, int[] v, long e)
{
for(int i = 0;i < v.length;i++){
if(v[i] >= mod)v[i] %= mod;
}
int[][] MUL = A;
for(;e > 0;e>>>=1) {
if((e&1)==1)v = mul(MUL, v);
MUL = p2(MUL);
}
return v;
}
// int matrix*int vector
public static int[] mul(int[][] A, int[] v)
{
int m = A.length;
int n = v.length;
int[] w = new int[m];
for(int i = 0;i < m;i++){
long sum = 0;
for(int k = 0;k < n;k++){
sum += (long)A[i][k] * v[k];
if(sum >= BIG)sum -= BIG;
}
w[i] = (int)(sum % mod);
}
return w;
}
// int matrix^2 (be careful about negative value)
public static int[][] p2(int[][] A)
{
int n = A.length;
int[][] C = new int[n][n];
for(int i = 0;i < n;i++){
long[] sum = new long[n];
for(int k = 0;k < n;k++){
for(int j = 0;j < n;j++){
sum[j] += (long)A[i][k] * A[k][j];
if(sum[j] >= BIG)sum[j] -= BIG;
}
}
for(int j = 0;j < n;j++){
C[i][j] = (int)(sum[j] % mod);
}
}
return C;
}
}
public static int lca2(int a, int b, int[][] spar, int[] depth) {
if (depth[a] < depth[b]) {
b = ancestor(b, depth[b] - depth[a], spar);
} else if (depth[a] > depth[b]) {
a = ancestor(a, depth[a] - depth[b], spar);
}
if (a == b)
return a;
int sa = a, sb = b;
for (int low = 0, high = depth[a], t = Integer.highestOneBit(high), k = Integer
.numberOfTrailingZeros(t); t > 0; t >>>= 1, k--) {
if ((low ^ high) >= t) {
if (spar[k][sa] != spar[k][sb]) {
low |= t;
sa = spar[k][sa];
sb = spar[k][sb];
} else {
high = low | t - 1;
}
}
}
return spar[0][sa];
}
protected static int ancestor(int a, int m, int[][] spar) {
for (int i = 0; m > 0 && a != -1; m >>>= 1, i++) {
if ((m & 1) == 1)
a = spar[i][a];
}
return a;
}
public static int[][] logstepParents(int[] par) {
int n = par.length;
int m = Integer.numberOfTrailingZeros(Integer.highestOneBit(n - 1)) + 1;
int[][] pars = new int[m][n];
pars[0] = par;
for (int j = 1; j < m; j++) {
for (int i = 0; i < n; i++) {
pars[j][i] = pars[j - 1][i] == -1 ? -1
: pars[j - 1][pars[j - 1][i]];
}
}
return pars;
}
public static int[] decomposeToHeavyLight(int[][] g, int[] par, int[] ord) {
int n = g.length;
int[] size = new int[n];
Arrays.fill(size, 1);
for (int i = n - 1; i > 0; i--)
size[par[ord[i]]] += size[ord[i]];
int[] clus = new int[n];
Arrays.fill(clus, -1);
int p = 0;
outer: for (int i = 0; i < n; i++) {
int u = ord[i];
if (clus[u] == -1)
clus[u] = p++;
for (int v : g[u]) {
if (par[u] != v && size[v] >= size[u] / 2) {
clus[v] = clus[u];
continue outer;
}
}
for (int v : g[u]) {
if (par[u] != v) {
clus[v] = clus[u];
break;
}
}
}
return clus;
}
public static int[][] clusPaths(int[] clus, int[] ord) {
int n = clus.length;
int[] rp = new int[n];
int sup = 0;
for (int i = 0; i < n; i++) {
rp[clus[i]]++;
sup = Math.max(sup, clus[i]);
}
sup++;
int[][] row = new int[sup][];
for (int i = 0; i < sup; i++)
row[i] = new int[rp[i]];
for (int i = n - 1; i >= 0; i--) {
row[clus[ord[i]]][--rp[clus[ord[i]]]] = ord[i];
}
return row;
}
public static int[] clusIInd(int[][] clusPath, int n) {
int[] iind = new int[n];
for (int[] path : clusPath) {
for (int i = 0; i < path.length; i++) {
iind[path[i]] = i;
}
}
return iind;
}
public static int[][] parentToG(int[] par)
{
int n = par.length;
int[] ct = new int[n];
for(int i = 0;i < n;i++){
if(par[i] >= 0){
ct[i]++;
ct[par[i]]++;
}
}
int[][] g = new int[n][];
for(int i = 0;i < n;i++){
g[i] = new int[ct[i]];
}
for(int i = 0;i < n;i++){
if(par[i] >= 0){
g[par[i]][--ct[par[i]]] = i;
g[i][--ct[i]] = par[i];
}
}
return g;
}
public static int[][] parents3(int[][] g, int root) {
int n = g.length;
int[] par = new int[n];
Arrays.fill(par, -1);
int[] depth = new int[n];
depth[0] = 0;
int[] q = new int[n];
q[0] = root;
for (int p = 0, r = 1; p < r; p++) {
int cur = q[p];
for (int nex : g[cur]) {
if (par[cur] != nex) {
q[r++] = nex;
par[nex] = cur;
depth[nex] = depth[cur] + 1;
}
}
}
return new int[][] { par, q, depth };
}
static int[][] packU(int n, int[] from, int[] to) {
int[][] g = new int[n][];
int[] p = new int[n];
for (int f : from)
p[f]++;
for (int t : to)
p[t]++;
for (int i = 0; i < n; i++)
g[i] = new int[p[i]];
for (int i = 0; i < from.length; i++) {
g[from[i]][--p[from[i]]] = to[i];
g[to[i]][--p[to[i]]] = from[i];
}
return g;
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new H().run(); }
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
Problem solution in C++ programming.
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <climits>
#include <cctype>
#include <utility>
#include <queue>
#include <cmath>
#include <complex>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
typedef pair<LL, LL> PLL;
typedef pair<int, LL> PIL;
typedef pair<LL, int> PLI;
typedef double DB;
#define pb push_back
#define mset(a, b) memset(a, b, sizeof a)
#define all(x) (x).begin(), (x).end()
#define bit(x) (1 << (x))
#define bitl(x) (1LL << (x))
#define sqr(x) ((x) * (x))
#define sz(x) ((int)(x.size()))
#define cnti(x) (__builtin_popcount(x))
#define cntl(x) (__builtin_popcountll(x))
#define clzi(x) (__builtin_clz(x))
#define clzl(x) (__builtin_clzll(x))
#define ctzi(x) (__builtin_ctz(x))
#define ctzl(x) (__builtin_ctzll(x))
#define X first
#define Y second
#define Error(x) cout << #x << " = " << x << endl
template <typename T, typename U>
inline void chkmax(T& x, U y) {
if (x < y) x = y;
}
template <typename T, typename U>
inline void chkmin(T& x, U y) {
if (y < x) x = y;
}
const int MOD = 1e9 + 7;
const int MAXN = 111111;
int n, m;
VI adj[MAXN];
int f[17][MAXN];
int d[MAXN], st[MAXN], en[MAXN];
int b[3][MAXN];
int c[55][2][2];
int T;
void dfs(int u) {
st[u] = ++T;
for (int i = 0; i < sz(adj[u]); i++) {
d[adj[u][i]] = d[u] + 1;
dfs(adj[u][i]);
}
en[u] = T;
}
void add(int p, int id, int x) {
for (; p <= n; p += p & -p) {
b[id][p] = (b[id][p] + x) % MOD;
}
}
int get_sum(int p, int id) {
int ret = 0;
for (; p; p -= p & -p) {
ret = (ret + b[id][p]) % MOD;
}
return ret;
}
PII get(LL e) {
int a[2], _a[2]; a[0] = 1, a[1] = 0;
for (int i = 50; i >= 0; i--) {
if (e >> i & 1) {
for (int j = 0; j < 2; j++) {
LL s = 0;
for (int k = 0; k < 2; k++) {
s += (LL)a[k] * c[i][j][k];
}
_a[j] = s % MOD;
}
memcpy(a, _a, sizeof a);
}
}
return make_pair(a[0], a[1]);
}
inline int lca(int u, int v) {
if (d[u] < d[v]) swap(u, v);
for (int i = 16; i >= 0; i--) {
if (d[f[i][u]] < d[v]) continue;
u = f[i][u];
if (d[u] == d[v]) break;
}
if (u == v) return u;
for (int i = 16; i >= 0; i--) {
if (f[i][u] == f[i][v]) continue;
u = f[i][u], v = f[i][v];
}
return f[0][u];
}
void change(int u, LL k) {
k += 2*(MOD+1);
PII x = get(k), y = get(k - d[u] + 1);
add(st[u], 0, MOD-x.first);
add(st[u], 1, y.first);
add(st[u], 2, y.second);
add(en[u]+1, 0, x.first);
add(en[u]+1, 1, MOD-y.first);
add(en[u]+1, 2, MOD-y.second);
}
int query(int u) {
if (!u) {
return 0;
}
PII x = get(d[u]);
LL s0 = get_sum(st[u], 0), s1 = get_sum(st[u], 1), s2 = get_sum(st[u], 2);
return (s0 + s1 * x.first + s2 * x.second) % MOD;
}
int main() {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
c[0][i][j] = !(i & j);
}
}
for (int e = 1; e <= 50; e++) {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
LL s = 0;
for (int k = 0; k < 2; k++) {
s += (LL)c[e-1][i][k] * c[e-1][k][j];
}
c[e][i][j] = s % MOD;
}
}
}
scanf("%d%d", &n, &m);
for (int i = 2; i <= n; i++) {
int x; scanf("%d", &x);
adj[x].push_back(i), f[0][i] = x;
}
d[1] = 1;
dfs(1);
for (int i = 1; i <= 16; i++) {
for (int j = 1; j <= n; j++) {
f[i][j] = f[i-1][f[i-1][j]];
}
}
memset(b, 0, sizeof b);
for (int i = 0; i < m; i++) {
char t[5]; int u;
scanf("%s%d", t, &u);
if (t[0] == 'U') {
LL k; scanf("%lld", &k);
change(u, k);
} else {
int v; scanf("%d", &v);
int w = lca(u, v), p = f[0][w], ans = 0;
ans = (query(u)+query(v)) % MOD;
ans = (ans+MOD-query(w)) % MOD;
ans = (ans+MOD-query(p)) % MOD;
printf("%dn", ans);
}
}
return 0;
}
Problem solution in C programming.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define prime_base 1000000007
#define fib_cycle_mag 2000000016L
static inline int mod_prime_base(int self) {
return (self % prime_base) + (prime_base & (self >> 31));
}
static inline int mod_long_prime(long self) {
return (int)((self % (long)prime_base) + ((long)prime_base & (self >> 63)));
}
static inline unsigned mod_fib_cycle(long self) {
return (unsigned)((self % fib_cycle_mag) + (fib_cycle_mag & (self >> 63)));
}
unsigned cached_fib[1 << 20] = {0};
#define array_cnt(self) (sizeof(self)/sizeof((self)[0]))
void init_cached_fib() {
unsigned at, prev = 1, next = 1;
for (at = 1; at < array_cnt(cached_fib); at++) {
cached_fib[at] = prev;
prev = next;
next += cached_fib[at];
next %= prime_base;
}
}
unsigned fib(unsigned self) {
if (self < array_cnt(cached_fib))
return cached_fib[self];
if (self & 1U) {
self = (self + 1) >> 1;
unsigned long
self_fib = fib(self),
other_fib = fib(self - 1);
return (unsigned)((self_fib * self_fib + other_fib * other_fib) % prime_base);
}
unsigned long self_fib = fib(self >>= 1);
return (unsigned)((self_fib * ((fib(self - 1) << 1) + self_fib)) % prime_base);
}
typedef int sum_t;
static inline sum_t bit_sum(unsigned length, sum_t self[length], unsigned node) {
sum_t total = 0;
for (; node; node &= node - 1)
total = mod_prime_base(total + self[node]);
return total;
}
static inline void bit_update(unsigned length, sum_t self[length], unsigned node, sum_t delta) {
for (; node < length; node += node & -node)
self[node] = mod_prime_base(self[node] + delta);
}
static inline void bit_point_range_update(unsigned length, sum_t sums[length], unsigned low, unsigned high, sum_t delta) {
bit_update(length, sums, low, delta);
bit_update(length, sums, high + 1, mod_prime_base(-delta));
}
static inline unsigned log2_floor(unsigned self) {
static unsigned debruijn[] = {
0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};
self |= self >> 1;
self |= self >> 2;
self |= self >> 4;
self |= self >> 8;
self |= self >> 16;
return debruijn[(self * 0x07C4ACDDU) >> 27];
}
unsigned nearest_common_ancestor(
unsigned vertex_cnt,
unsigned log2_dists,
unsigned ancestors[log2_dists][vertex_cnt],
unsigned *depths,
unsigned source,
unsigned target
) {
if (depths[source] < depths[target]) {
source ^= target;
target ^= source;
source ^= target;
}
for (; depths[target] < depths[source]; source = ancestors[log2_floor(depths[source] - depths[target])][source]);
if (source == target)
return source;
unsigned low = 0;
while ((depths[source] - low) > 1) {
unsigned mid = log2_floor((depths[source] - low) >> 1);
if (ancestors[mid][source] != ancestors[mid][target]) {
source = ancestors[mid][source];
target = ancestors[mid][target];
} else
low = depths[ancestors[mid][source]];
}
return ancestors[0][source];
}
static inline sum_t tree_path_sum(unsigned length, sum_t sums[3][length], unsigned *depths, unsigned *ids, unsigned at) {
return mod_long_prime(
(long)cached_fib[depths[at]] * bit_sum(length, sums[0], ids[at])
+ (long)cached_fib[depths[at] + 1] * bit_sum(length, sums[1], ids[at])
- bit_sum(length, sums[2], ids[at])
);
}
int main() {
init_cached_fib();
unsigned at, vertex_cnt, queries;
scanf("%u %u", &vertex_cnt, &queries);
unsigned
log2_dists = log2_floor(vertex_cnt) + 1,
ancestors[log2_dists][vertex_cnt + 1],
*descendants = memset(
malloc(5 * (vertex_cnt + 1) * sizeof(unsigned)), 0, sizeof(unsigned) * ((vertex_cnt + 1) << 1)
),
*indices = &descendants[vertex_cnt + 1],
*weights = &indices[vertex_cnt + 1],
*ids = &weights[vertex_cnt + 1],
*depths = &ids[vertex_cnt + 1];
ancestors[0][1] = 0;
indices[0] = 1;
for (at = 2; at <= vertex_cnt; indices[ancestors[0][at++]]++)
scanf("%u", &ancestors[0][at]);
for (at = 0; at < log2_dists; ancestors[at++][0] = 0);
for (at = 0; ++at <= vertex_cnt; indices[at] += indices[at - 1]);
for (at = vertex_cnt + 1; --at; descendants[--indices[ancestors[0][at]]] = at);
{
unsigned history[vertex_cnt + 1];
memset(weights, 0, sizeof(weights[0]) * sizeof(unsigned));
depths[0] = 0;
history[0] = 0;
for (at = 1; at;) {
unsigned
root = history[at - 1],
others = indices[root];
if (weights[root]) {
for (; ancestors[0][descendants[others]] == root; weights[root] += weights[descendants[others++]]);
at--;
} else
for (weights[root] = 1; ancestors[0][descendants[others]] == root;
history[at++] = descendants[others++])
depths[descendants[others]] = depths[root] + 1;
}
ids[0] = 0;
history[0] = 0;
for (at = 1; at;) {
unsigned
weight = 1,
root = history[--at],
others = indices[root];
for (; ancestors[0][descendants[others]] == root; weight += weights[descendants[others++]]) {
history[at++] = descendants[others];
ids[descendants[others]] = ids[root] + weight;
}
}
}
unsigned level;
for (level = 1; level < log2_dists; level++)
for (at = 0; ++at <= vertex_cnt;
ancestors[level][at] = ancestors[level - 1][ancestors[level - 1][at]]);
sum_t sums[3][++vertex_cnt];
memset(sums, 0, sizeof(sums));
long kth_fib;
for (getchar(); queries--; getchar())
if (getchar() == 'U') {
scanf("%u %ld", &at, &kth_fib);
long kth_fibs[2] = {
fib(mod_fib_cycle(kth_fib)),
fib(mod_fib_cycle(kth_fib + 1))
}, *low_fibs = &(((long [3]){
[2] = fib(depths[at]),
[1] = fib(depths[at] - 1),
[0] = fib(((depths[at] > 1) ? (depths[at] - 2) : 1))
})[2]);
#define odd_mask(self) (((int)((self) << 31) >> 30) | 1)
bit_point_range_update(
vertex_cnt,
sums[0],
ids[at],
ids[at] + weights[at] - 1,
mod_long_prime(odd_mask(depths[at]) * (kth_fibs[1] * low_fibs[-1UL] - kth_fibs[0] * low_fibs[0]))
);
bit_point_range_update(
vertex_cnt,
sums[1],
ids[at],
ids[at] + weights[at] - 1,
mod_long_prime(odd_mask(depths[at]) * (kth_fibs[0] * low_fibs[-1UL] - kth_fibs[1] * low_fibs[-2UL]))
);
bit_point_range_update(
vertex_cnt,
sums[2],
ids[at],
ids[at] + weights[at] - 1,
(unsigned)kth_fibs[1]
);
} else {
unsigned source, target, common;
scanf("%u %u", &source, &target);
common = nearest_common_ancestor(vertex_cnt, log2_dists, ancestors, depths, source, target);
printf("%dn",
mod_long_prime(
(long)tree_path_sum(vertex_cnt, sums, depths, ids, source)
+ tree_path_sum(vertex_cnt, sums, depths, ids, target)
- tree_path_sum(vertex_cnt, sums, depths, ids, common)
- tree_path_sum(vertex_cnt, sums, depths, ids, ancestors[0][common])
)
);
}
free(descendants);
return 0;
}