Answer to Question #293874 in Python for Gowri

Question

Given a weighted undirected tree of N nodes and Q queries. Each query contains an integer D. For each query, find the number of paths in the given tree such that all the edges in the path

are divisible by D.

put Format:

First line contains two space separated integers, N and Q (1 ≤ N.Q < 10³), denoting number of nodes in the tree and number of queries. Next N 1 ine contains three space separated integer Y and W[1 < X,Y <N] (1< W< 10³), denoting that there is an edge between X and Y of weight W. Next Qlines contains one integer each, 0(1 <D≤ 10').

Answer 1

import math
N = 100005;

level = [0 for i in range(N)]
LG = 20;

dp = [[0 for j in range(N)]
		for i in range(LG)]

mx = [[0 for j in range(N)]
		for i in range(LG)]

v = [[] for i in range(N)]
n = 0

def dfs_lca(a, par, lev):


	dp[0][a] = par;
	level[a] = lev;
	
	for i in v[a]:

		if (i[0] == par):
			continue;
		mx[0][i[0]] = i[1];

		dfs_lca(i[0], a, lev + 1);

def find_ancestor():

	for i in range(1, 16):
	
		for j in range(1, n + 1):
		
			dp[i][j] = dp[i - 1][dp[i - 1][j]];

			mx[i][j] = max(mx[i - 1][j],
						mx[i - 1][dp[i - 1][j]]);


def getMax(a, b):

	if (level[b] < level[a]):
		a, b = b, a


	ans = 0;


	diff = level[b] - level[a];
	
	while (diff > 0):
		log = int(math.log2(diff));
		ans = max(ans, mx[log][b]);

		b = dp[log][b];

		diff -= (1 << log);
	
	while (a != b):
		i = int(math.log2(level[a]));

		while (i > 0 and
			dp[i][a] == dp[i][b]):
			i-=1

		ans = max(ans, mx[i][a]);
		ans = max(ans, mx[i][b]);

		a = dp[i][a];
		b = dp[i][b];
	
	return ans;

def compute_lca():
	
	dfs_lca(1, 0, 0);
	find_ancestor();

if __name__=="__main__":
	
	
	n = 5;
	v[1].append([2, 2]);
	v[2].append([1, 2]);
	v[1].append([3, 5]);
	v[3].append([1, 5]);
	v[3].append([4, 3]);
	v[4].append([3, 4]);
	v[3].append([5, 1]);
	v[5].append([3, 1]);

	compute_lca();


	queries= [[3, 5], [2, 3], [2,4]]
	q = 3;
	
	for i in range(q):
		max_edge = getMax(queries[i][0],
						queries[i][1]);
		print(max_edge)