In this HackerRank Lazy White Falcon problem, we have given a tree with N nodes where each node's value is initially 0 and we need to execute Q queries.
Problem solution in Python programming.
#!/bin/python3
import os
import sys
import math
sys.setrecursionlimit(10**6)
def roundup(x):
k = 1 << (x.bit_length()-1)
if k < x:
return 2*k
return k
def update(t,i,x,op):
t[i] = x
while i > 1:
i >>= 1
t[i] = op(t[2*i],t[2*i+1])
def rangequery(t,a,b,op,init): # assumes op is of abelian monoid
s = init
while a < b:
if a & 1:
s = op(s,t[a])
a += 1
if b & 1:
s = op(s,t[b-1])
b -= 1
a >>= 1
b >>= 1
return s
def rangeify(l,op,init):
off = roundup(len(l))
r = [init for _ in range(off)] + l + [init for _ in range(off-len(l))]
for i in range(off-1,0,-1):
r[i] = op(r[2*i],r[2*i+1])
return (r,off)
# Complete the solve function below.
def solve(tree, queries):
N = len(tree) + 1
neighbors = [[] for _ in range(N)]
for edge in tree:
neighbors[edge[0]].append(edge[1])
neighbors[edge[1]].append(edge[0])
heights = []
eulerian = []
outs = []
epos = [[-1,-1] for _ in range(N)]
heightpos = [-1 for _ in range(N)]
def dfs(node, parent, height):
eulerian.append(0)
epos[node][0] = len(eulerian)-1
heights.append((height,node))
heightpos[node] = len(heights) - 1
for n in neighbors[node]:
if n != parent:
dfs(n, node, height+1)
heights.append((height,node))
eulerian.append(0)
epos[node][1] = len(eulerian) - 1
dfs(0,-1,0)
htree, hoff = rangeify(heights,lambda x,y: min(x,y), (math.inf,math.inf))
eulerian, off = rangeify(eulerian, lambda x,y: x+y, 0)
epos = [[x[0]+off,x[1]+off] for x in epos]
heightpos = [x + hoff for x in heightpos]
def lca(u,v):
low, high = heightpos[u],heightpos[v]
low, high = min(low,high),max(low,high)
return rangequery(htree,
low,
high+1,
lambda x,y: min(x,y),
(math.inf,math.inf))
def pathsum(u,v):
a = lca(u,v)[1]
ou = rangequery(eulerian,epos[0][0],epos[u][0]+1,lambda x,y: x+y,0)
ov = rangequery(eulerian,epos[0][0],epos[v][0]+1,lambda x,y: x+y,0)
oa = rangequery(eulerian,epos[0][0],epos[a][0]+1,lambda x,y: x+y,0)
return ou + ov - 2*oa + eulerian[epos[a][0]]
for query in queries:
if query[0] == 1:
u = query[1]
x = query[2]
update(eulerian,epos[u][0],x,lambda x,y: x+y)
update(eulerian,epos[u][1],-x,lambda x,y: x+y)
else:
u = query[1]
v = query[2]
outs.append(pathsum(u,v))
print(htree)
print(heightpos)
print(epos)
print(eulerian, off)
return outs
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
nq = input().split()
n = int(nq[0])
q = int(nq[1])
tree = []
for _ in range(n-1):
tree.append(list(map(int, input().rstrip().split())))
queries = []
for _ in range(q):
queries.append(list(map(int, input().rstrip().split())))
result = solve(tree, queries)
fptr.write('\n'.join(map(str, result)))
fptr.write('\n')
fptr.close()Problem solution in Java Programming.
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
import java.util.stream.Collectors;
class Node {
int id;
Node parent;
List<Node> children;
List<Node> connections;
int value;
public Node(int id) {
this.id = id;
this.children = new LinkedList<>();
this.connections = new LinkedList<>();
}
public void addConnection(Node c) {
this.connections.add(c);
}
public void addChild(Node child) {
this.children.add(child);
child.parent = this;
}
public void updateValue(int nodeId, int value) {
Node toUpdateNode = nodes[nodeId];
int increment = value - toUpdateNode.value;
toUpdateNode.value = value;
int firstEuler = eulerFirsts[toUpdateNode.id],
lastEuler = eulerLasts[toUpdateNode.id];
int startIndex = Math.min(firstEuler, lastEuler),
endIndex = Math.max(firstEuler, lastEuler);
this.rootAggregates.update(startIndex, endIndex, increment);
}
public int rootAggregation(int nodeId) {
Node toUpdateNode = nodes[nodeId];
int firstEuler = eulerFirsts[toUpdateNode.id];
return this.rootAggregates.get(firstEuler);
}
public boolean isParent(Node another) {
return this.parent != null && this.parent.id == another.id;
}
public int LCAIndex(int n1, int n2) {
int n1EulerAppearance = eulerFirsts[n1],
n2EulerAppearance = eulerFirsts[n2];
int startIndex = Math.min(n1EulerAppearance, n2EulerAppearance),
endIndex = Math.max(n1EulerAppearance, n2EulerAppearance) + 1;
EulerNode lcaNode = eulerNodes.min(startIndex, endIndex);
return lcaNode.vertex;
}
private int[] eulerFirsts;
private int[] eulerLasts;
private int[] eulerPath;
private Node[] nodes;
private SegmentTreeSegmentedAddition rootAggregates;
private SegmentTreeMin<EulerNode> eulerNodes;
public void processLCA(Node[] nodes) {
this.nodes = nodes;
boolean[] visited = new boolean[nodes.length];
this.eulerFirsts = new int[nodes.length];
Arrays.fill(this.eulerFirsts, -1);
this.eulerLasts = new int[nodes.length];
Arrays.fill(this.eulerLasts, -1);
LinkedList<Integer> eulerHeights = new LinkedList<>();
LinkedList<Node> stack = new LinkedList<>(),
eulerPath = new LinkedList<>();
stack.push(this);
int depth = 1;
while(!stack.isEmpty()) {
Node current = stack.pop();
eulerPath.add(current);
eulerHeights.add(depth);
int eulerLength = eulerPath.size() - 1;
if (this.eulerFirsts[current.id] == -1) {
this.eulerFirsts[current.id] = eulerLength;
}
if (this.eulerLasts[current.id] == -1 || eulerLength > this.eulerLasts[current.id]) {
this.eulerLasts[current.id] = eulerLength;
}
if (!visited[current.id]) {
visited[current.id] = true;
for (Node child : current.children) {
stack.push(current);
stack.push(child);
}
}
Node next = stack.peekFirst();
if (next != null && next.isParent(current)) depth++;
else depth--;
}
int[] vertices = eulerPath.stream().mapToInt(n -> n.id).toArray();
int[] heights = eulerHeights.stream().mapToInt(Integer::intValue).toArray();
EulerNode[] eulerNodes = new EulerNode[eulerPath.size()];
for (int i = 0; i < heights.length; i++) {
eulerNodes[i] = new EulerNode(heights[i], vertices[i]);
}
this.eulerNodes = new SegmentTreeMin<>(eulerNodes);
this.eulerPath = vertices;
this.rootAggregates = new SegmentTreeSegmentedAddition( new int[this.eulerPath.length] );
}
public void processRoot() {
LinkedList<Node> stack = new LinkedList<>();
stack.push(this);
while (!stack.isEmpty()) {
Node current = stack.pop();
for (Node connection : current.connections) {
if (connection == current || connection == current.parent) continue;
stack.push(connection);
current.addChild(connection);
}
}
}
}
class EulerNode implements Comparable {
int height;
int vertex;
public EulerNode(int height, int vertex) {
this.height = height;
this.vertex = vertex;
}
@Override
public int compareTo(Object o) {
EulerNode other = (EulerNode)o;
return this.height - other.height;
}
}
class SegmentTreeSegmentedAddition {
private int[] values;
private int[] tree;
public SegmentTreeSegmentedAddition(int[] values) {
this.values = values;
this.tree = new int[values.length * 4];
build(1, 0, values.length - 1);
}
private void build(int v, int tl, int tr) {
if (tl == tr) {
tree[v] = values[tl];
} else {
int tm = (tl + tr) / 2;
build(v * 2, tl, tm);
build(v * 2 + 1, tm + 1, tr);
tree[v] = 0;
}
}
public void update(int l, int r, int add) {
this.update(1, 0, values.length - 1, l, r, add);
}
private void update(int v, int tl, int tr, int l, int r, int add) {
if (l > r)
return;
if (l == tl && r == tr) {
tree[v] += add;
} else {
int tm = (tl + tr) / 2;
update(v * 2, tl, tm, l, Math.min(r, tm), add);
update(v * 2 + 1, tm + 1, tr, Math.max(l, tm + 1), r, add);
}
}
public int get(int pos) {
return this.get(1, 0, values.length - 1, pos);
}
private int get(int v, int tl, int tr, int pos) {
if (tl == tr)
return tree[v];
int tm = (tl + tr) / 2;
if (pos <= tm)
return tree[v] + get(v * 2, tl, tm, pos);
else
return tree[v] + get(v * 2 + 1, tm + 1, tr, pos);
}
}
class SegmentTreeMin<T extends Comparable> {
private T[] values;
private ArrayList<T> tree;
public SegmentTreeMin(T[] values) {
this.values = values;
this.tree = new ArrayList<T>(this.values.length * 4);
for (int i = 0; i < this.values.length * 4; i++) {
this.tree.add(null);
}
build(1, 0, values.length - 1);
}
private void build(int v, int tl, int tr) {
if (tl == tr) {
tree.set(v, values[tl]);
} else {
int tm = (tl + tr) / 2;
build(v * 2, tl, tm);
build(v * 2 + 1, tm + 1, tr);
T left = tree.get(v * 2),
right = tree.get(v * 2 + 1);
tree.set(v, left.compareTo(right) < 0 ? left : right);
}
}
public T min(int l, int r) {
return min(1, 0, values.length - 1, l, r);
}
private T min(int v, int tl, int tr, int l, int r) {
if (l > r)
return null; // return value that will not affect the reduction
if (l == tl && r == tr) {
return tree.get(v);
}
int tm = (tl + tr) / 2;
T min1 = min(v*2, tl, tm, l, Math.min(r, tm)),
min2 = min(v*2+1, tm+1, tr, Math.max(l, tm+1), r);
if (min1 == null && min2 == null) throw new NullPointerException("Cannot retrieve minimum value from 2 nulls");
else if (min1 == null) return min2;
else if (min2 == null) return min1;
else return min1.compareTo(min2) < 0 ? min1 : min2;
}
}
public class Solution {
static int[] solve(int[][] edges, int[][] queries) {
List<Integer> result = new LinkedList<>();
Node[] nodes = new Node[edges.length + 1];
for (int i = 0; i < edges.length; i++) {
int[] link = edges[i];
int n1 = link[0], n2 = link[1];
Node node1 = nodes[n1] != null ? nodes[n1] : new Node(n1),
node2 = nodes[n2] != null ? nodes[n2] : new Node(n2);
node1.addConnection(node2);
node2.addConnection(node1);
nodes[n1] = node1;
nodes[n2] = node2;
}
Node root = nodes[0];
root.processRoot();
root.processLCA(nodes);
for (int[] query : queries) {
int operation = query[0], arg1 = query[1], arg2 = query[2];
if (operation == 1) { // update value
root.updateValue(arg1, arg2);
} else if (operation == 2) { // print path aggregation
if (arg1 == arg2) {
result.add(nodes[arg1].value);
}
else {
int lcaIndex = root.LCAIndex(arg1, arg2);
int lcaValue = root.rootAggregation(nodes[lcaIndex].id),
n1Aggregation = root.rootAggregation(nodes[arg1].id),
n2Aggregation = root.rootAggregation(nodes[arg2].id);
int rootAggregationOffset = 0;
if (lcaIndex != root.id) {
rootAggregationOffset += root.rootAggregation(nodes[lcaIndex].parent.id);
}
int aggregation = n1Aggregation + n2Aggregation - lcaValue - rootAggregationOffset;
result.add( aggregation );
}
}
}
return result.stream().mapToInt(Integer::intValue).toArray();
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String[] nq = scanner.nextLine().split(" ");
int n = Integer.parseInt(nq[0]);
int q = Integer.parseInt(nq[1]);
int[][] tree = new int[n-1][2];
for (int treeRowItr = 0; treeRowItr < n-1; treeRowItr++) {
String[] treeRowItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int treeColumnItr = 0; treeColumnItr < 2; treeColumnItr++) {
int treeItem = Integer.parseInt(treeRowItems[treeColumnItr]);
tree[treeRowItr][treeColumnItr] = treeItem;
}
}
int[][] queries = new int[q][3];
for (int queriesRowItr = 0; queriesRowItr < q; queriesRowItr++) {
String[] queriesRowItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int queriesColumnItr = 0; queriesColumnItr < 3; queriesColumnItr++) {
int queriesItem = Integer.parseInt(queriesRowItems[queriesColumnItr]);
queries[queriesRowItr][queriesColumnItr] = queriesItem;
}
}
int[] result = solve(tree, queries);
for (int resultItr = 0; resultItr < result.length; resultItr++) {
bufferedWriter.write(String.valueOf(result[resultItr]));
if (resultItr != result.length - 1) {
bufferedWriter.write("\n");
}
}
bufferedWriter.newLine();
bufferedWriter.close();
scanner.close();
}
}Problem solution in C++ programming.
#include <bits/stdc++.h>
using namespace std;
vector<string> split_string(string);
struct Node
{
int path;
int size;
int depth;
int parent;
};
struct Path
{
int root;
int depth;
int size;
vector<int> sums;
int sum(int ti, int tl, int tr, int l, int r)
{
if (l <= r)
{
if (l == tl && r == tr)
{
return sums[ti];
}
else
{
int tm = (tl + tr) / 2;
return sum(2 * ti, tl, tm, l, min(r, tm)) + sum(2 * ti + 1, tm + 1, tr, max(l, tm + 1), r);
}
}
return 0;
}
void assign(int value, int ti, int tl, int tr, int i)
{
if (i == tl && i == tr)
{
sums[ti] = value;
}
else
{
int tm = (tl + tr) / 2;
if (i <= tm)
{
assign(value, 2 * ti, tl, tm, i);
}
else
{
assign(value, 2 * ti + 1, tm + 1, tr, i);
}
sums[ti] = sums[2 * ti] + sums[2 * ti + 1];
}
}
void assign(int i, int v)
{
assign(v, 1, 0, size - 1, i);
}
int sum(int l, int r)
{
return sum(1, 0, size - 1, l, r);
}
Path(int root, int depth, int size) : root(root), depth(depth), size(size)
{
int temp = 1;
while (temp <= size)
{
temp <<= 1;
}
sums.resize(2 * temp, 0);
}
};
class Tree
{
vector<Path> paths;
vector<Node> nodes;
bool isHeavy(int node)
{
int parent = nodes[node].parent;
return (parent < 0) ? false : (2 * nodes[node].size >= nodes[parent].size);
}
public:
Tree(vector<vector<int>>& edges)
{
vector<vector<int>> tree(edges.size() + 1);
for (int i = 0; i < edges.size(); i++)
{
tree[edges[i][0]].push_back(edges[i][1]);
tree[edges[i][1]].push_back(edges[i][0]);
}
nodes.resize(edges.size() + 1);
init(0, -1, 0, tree);
createPaths(0, -1, tree);
}
void init(int curr, int parent, int depth, vector<vector<int>>& tree)
{
nodes[curr].size = 1;
nodes[curr].depth = depth;
nodes[curr].parent = parent;
for (int i = 0; i < tree[curr].size(); i++)
{
int next = tree[curr][i];
if (next != parent)
{
init(next, curr, depth + 1, tree);
nodes[curr].size += nodes[next].size;
}
}
}
void createPaths(int curr, int parent, vector<vector<int>>& tree)
{
bool hasHeavy = false;
for (int i = 0; i < tree[curr].size(); i++)
{
int next = tree[curr][i];
if (next != parent)
{
createPaths(next, curr, tree);
if (isHeavy(next))
{
hasHeavy = true;
}
}
}
if (!hasHeavy)
{
createPath(curr);
}
}
void createPath(int node)
{
int length = 1;
while (true)
{
nodes[node].path = paths.size();
if (!isHeavy(node))
{
break;
}
node = nodes[node].parent;
length += 1;
}
paths.push_back(Path(node, nodes[node].depth, length));
}
void assign(int node, int value)
{
int path = nodes[node].path;
paths[path].assign(nodes[node].depth - paths[path].depth, value);
}
int sum(int u, int v)
{
if (nodes[u].path == nodes[v].path)
{
int path = nodes[u].path;
int l = std::min(nodes[u].depth, nodes[v].depth);
int r = std::max(nodes[u].depth, nodes[v].depth);
return paths[path].sum(l - paths[path].depth, r - paths[path].depth);
}
int rootU = paths[nodes[u].path].root;
int rootV = paths[nodes[v].path].root;
if (nodes[rootU].depth < nodes[rootV].depth)
{
int path = nodes[v].path;
return paths[path].sum(0, nodes[v].depth - paths[path].depth) + sum(u, nodes[rootV].parent);
}
else
{
int path = nodes[u].path;
return paths[path].sum(0, nodes[u].depth - paths[path].depth) + sum(nodes[rootU].parent, v);
}
}
};
vector<int> solve(vector<vector<int>>& edges, vector<vector<int>>& queries)
{
Tree tree(edges);
vector<int> res;
for (int i = 0; i < queries.size(); i++)
{
if (queries[i][0] == 1)
{
tree.assign(queries[i][1], queries[i][2]);
}
else
{
res.push_back(tree.sum(queries[i][1], queries[i][2]));
}
}
return res;
}
int main()
{
ofstream fout(getenv("OUTPUT_PATH"));
string nq_temp;
getline(cin, nq_temp);
vector<string> nq = split_string(nq_temp);
int n = stoi(nq[0]);
int q = stoi(nq[1]);
vector<vector<int>> tree(n-1);
for (int tree_row_itr = 0; tree_row_itr < n-1; tree_row_itr++) {
tree[tree_row_itr].resize(2);
for (int tree_column_itr = 0; tree_column_itr < 2; tree_column_itr++) {
cin >> tree[tree_row_itr][tree_column_itr];
}
cin.ignore(numeric_limits<streamsize>::max(), '\n');
}
vector<vector<int>> queries(q);
for (int queries_row_itr = 0; queries_row_itr < q; queries_row_itr++) {
queries[queries_row_itr].resize(3);
for (int queries_column_itr = 0; queries_column_itr < 3; queries_column_itr++) {
cin >> queries[queries_row_itr][queries_column_itr];
}
cin.ignore(numeric_limits<streamsize>::max(), '\n');
}
vector<int> result = solve(tree, queries);
for (int result_itr = 0; result_itr < result.size(); result_itr++) {
fout << result[result_itr];
if (result_itr != result.size() - 1) {
fout << "\n";
}
}
fout << "\n";
fout.close();
return 0;
}
vector<string> split_string(string input_string) {
string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
return x == y and x == ' ';
});
input_string.erase(new_end, input_string.end());
while (input_string[input_string.length() - 1] == ' ') {
input_string.pop_back();
}
vector<string> splits;
char delimiter = ' ';
size_t i = 0;
size_t pos = input_string.find(delimiter);
while (pos != string::npos) {
splits.push_back(input_string.substr(i, pos - i));
i = pos + 1;
pos = input_string.find(delimiter, i);
}
splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));
return splits;
}Problem solution in C programming.
#include <stdio.h>
#include <stdlib.h>
typedef struct _lnode{
int x;
int w;
struct _lnode *next;
} lnode;
typedef struct _tree{
int sum;
} tree;
void insert_edge(int x,int y,int w);
void dfs0(int u);
void dfs1(int u,int c);
void preprocess();
int lca(int a,int b);
int sum(int v,int tl,
int tr,int l,int r,tree *t);
void update(int v,int tl,
int tr,int pos,int new_val,tree *t);
int min(int x,int y);
int max(int x,int y);
int solve(int x,int ancestor);
int N,cn,level[100000],DP[18][100000],
subtree_size[100000],special[100000],
node_chain[100000],node_idx[100000],
chain_head[100000],chain_len[100000]={0};
lnode *table[100000]={0};
tree *chain[100000];
int main(){
int Q,x,y,i;
scanf("%d%d",&N,&Q);
for(i=0;i<N-1;i++){
scanf("%d%d",&x,&y);
insert_edge(x,y,1);
}
preprocess();
while(Q--){
scanf("%d",&x);
switch(x){
case 1:
scanf("%d%d",&x,&y);
update(1,0,chain_len[node_chain[x]]
-1,node_idx[x],y,chain[node_chain[x]]);
break;
default:
scanf("%d%d",&x,&y);
i=lca(x,y);
printf("%d\n",
solve(x,i)+solve(y,i)-
sum(1,0,chain_len[node_chain[i]]
-1,node_idx[i],node_idx[i],chain[node_chain[i]]));
}
}
return 0;
}
void insert_edge(int x,int y,int w){
lnode *t=malloc(sizeof(lnode));
t->x=y;
t->w=w;
t->next=table[x];
table[x]=t;
t=malloc(sizeof(lnode));
t->x=x;
t->w=w;
t->next=table[y];
table[y]=t;
return;
}
void dfs0(int u){
lnode *x;
subtree_size[u]=1;
special[u]=-1;
for(x=table[u];x;x=x->next)
if(x->x!=DP[0][u]){
DP[0][x->x]=u;
level[x->x]=level[u]+1;
dfs0(x->x);
subtree_size[u]+=subtree_size[x->x];
if(special[u]==-1 ||
subtree_size[x->x]>subtree_size[special[u]])
special[u]=x->x;
}
return;
}
void dfs1(int u,int c){
lnode *x;
node_chain[u]=c;
node_idx[u]=chain_len[c]++;
for(x=table[u];x;x=x->next)
if(x->x!=DP[0][u])
if(x->x==special[u])
dfs1(x->x,c);
else{
chain_head[cn]=x->x;
dfs1(x->x,cn++);
}
return;
}
void preprocess(){
int i,j;
level[0]=0;
DP[0][0]=0;
dfs0(0);
for(i=1;i<18;i++)
for(j=0;j<N;j++)
DP[i][j] = DP[i-1][DP[i-1][j]];
cn=1;
chain_head[0]=0;
dfs1(0,0);
for(i=0;i<cn;i++)
chain[i]=(tree*)malloc(
4*chain_len[i]*sizeof(tree));
for(i=0;i<N;i++)
update(1,0,chain_len[node_chain[i]]-1,
node_idx[i],0,chain[node_chain[i]]);
return;
}
int lca(int a,int b){
int i;
if(level[a]>level[b]){
i=a;
a=b;
b=i;
}
int d = level[b]-level[a];
for(i=0;i<18;i++)
if(d&(1<<i))
b=DP[i][b];
if(a==b)return a;
for(i=17;i>=0;i--)
if(DP[i][a]!=DP[i][b])
a=DP[i][a],b=DP[i][b];
return DP[0][a];
}
int sum(int v,int tl,int tr,int l,
int r,tree *t){
if(l>r)
return 0;
if(l==tl && r==tr)
return t[v].sum;
int tm=(tl+tr)/2;
return sum(v*2,tl,tm,l,min(r,tm),t)+
sum(v*2+1,tm+1,tr,max(l,tm+1),r,t);
}
void update(int v,int tl,int tr,
int pos,int new_val,tree *t){
if(tl==tr)
t[v].sum=new_val;
else{
int tm=(tl+tr)/2;
if(pos<=tm)
update(v*2,tl,tm,pos,new_val,t);
else
update(v*2+1,tm+1,tr,pos,new_val,t);
t[v].sum=t[v*2].sum+t[v*2+1].sum;
}
}
int min(int x,int y){
return (x<y)?x:y;
}
int max(int x,int y){
return (x>y)?x:y;
}
int solve(int x,int ancestor){
int ans=0;
while(node_chain[x]!=node_chain[ancestor]){
ans+=sum(1,0,chain_len[node_chain[x]]-1,
0,node_idx[x],chain[node_chain[x]]);
x=DP[0][chain_head[node_chain[x]]];
}
ans+=sum(1,0,chain_len[node_chain[x]]-1,
node_idx[ancestor],node_idx[x],
chain[node_chain[x]]);
return ans;
}
0 Comments