CTYTRA Editorial

editorial
1

Problem Summary

Problem : City Travelling
Contest : Chef Dynasty

Editorialist & Author: Draco9421
Tester: ffiq

Difficulty: Easy-Medium
Prerequisites: Lowest Common Ancestor / Segment Tree / Range minimum query / dfs /bfs

PROBLEM STATEMENT

DYCUR is the currency popular in the Chef Dynasty. The Dynasty has control over N cities which are connected by directed roads. The construction of these roads as demanded by Chef was done in the form of a tree.
Every road has a direction in which the soldiers of Chef Dynasty permit the people to travel in. For going in the opposite direction, a person would have to bribe these soldiers with K DYCURS before crossing the road.
You are given Q queries each containing a single line with 2 space separated integers X and Y, denoting the source city and the destination city. You have to find the the total amount in DYCURS that a person has to carry to reach from city X to City Y.

Expanation :

To solve this problem you first need to know that what is LCA(Lowest Common Ancestor)
Following is definition of LCA: Let T be a rooted tree. The lowest common ancestor between two nodes n1 and n2 is defined as the lowest node in T that has both n1 and n2 as descendants.

Now as you know what is LCA let’s start with that how can you find LCA for the problems containing Queries the most easy approach can be by using the segment tree and range minimum query.

  • Firstly find the Euler Tour for the given tree.
  • Then you have to find the level for each node and assign it to the every node as represented by the array formed by using the step above .
  • Also you can keep the track of opposite edges you have to traverse to reach that respective node from the root
  • Now using that level array simply construct a segment tree which will help you to find the LCA using Range minimum Query in O(log(n)) time.
  • As you find the LCA you can simply find the number of opposite edge you have to traverse from node X to node Y by simply adding the correct and incorrect path of node X and node Y respectively and subtracting the correct and incorrect path of the LCA (here correct path is the direction in which the bridge is directed and vice versa)

You can check here for further infomation link

Solution :

Setter's Solution 
occ = []
visited1 = [0]*1000005
visited2 = [0]*1000005
visited3 = [0]*1000005
a = [0]*1000005
levels  = [0]*1000005
occ_by_levels = []
st = [0]*1000005
v = [[] for i in range(1000005)]
path = [[] for i in range(1000005)]
   
def occ_dfs(src): #for Euler Tour
        occ.append(src)
        visited1[src] = 1
        for i,j in v[src]:
                if(visited1[i] == 0):
                        occ_dfs(i)
                        occ.append(src)

def finding_level(src , cnt):
        levels[src] = cnt
        visited2[src] = 1
        for i,j in v[src]:
                if(visited2[i] == 0):
                        finding_level(i,cnt + 1)

def assign_levels():
        for i in range(0, len(occ)):
                occ_by_levels.append(levels[occ[i]])

        
def dfs(src , correct , incorrect , k): #finding the correct and incorrect path from the root
        if(visited3[src] == 0):
                visited3[src]= 1
                l = [correct, incorrect]
                path[src] = l
                for i,j in v[src]:
                        if(j == k):
                                dfs(i,correct,incorrect+1,k)
                        else:
                                dfs(i,correct+1,incorrect,k)

def RMQ(ss,  se,  qs,  qe,  i):
        if(se < qs or qe < ss):
                return -1
  
        if(qs <= ss and se <= qe):
                return st[i]
  
        mid = (ss + se) >> 1
        sp = RMQ(ss, mid, qs, qe, 2*i + 1) 
        en = RMQ(mid + 1, se, qs, qe, 2*i + 2) 
  
        if (sp != -1 and en != -1):
                if (occ_by_levels[sp] < occ_by_levels[en]): 
                        return sp
                return en
        elif (sp != -1):
                return sp 
        elif (en != -1):
                return en

  
def SegmentTreeConstruction(ss,  se,  i):

        if (ss > se):
                return
        if (ss == se):
                st[i] = ss
                return 
           
        mid = (ss + se) >> 1; 
          
        SegmentTreeConstruction(ss, mid, 2*i + 1); 
        SegmentTreeConstruction(mid + 1, se, 2*i + 2); 
          
        if (occ_by_levels[st[2*i + 1]] < occ_by_levels[st[2*i + 2]]):
            st[i] = st[2*i + 1] 
        else:
            st[i] = st[2*i + 2]

   
def LCA(x, y):
    if (a[x] > a[y]):
    	return occ[RMQ(0, len(occ_by_levels)-1, a[y], a[x], 0)]
    return occ[RMQ(0, len(occ_by_levels)-1, a[x], a[y], 0)] 



n, k = [int(x) for x in input().split()]
for i in range(0 , (n)-1):
        x , y = [int(k) for k in input().split()]
        pair1 = [y,int(0)]
        v[x].append(pair1)
        pair2 = [x,k]
        v[y].append(pair2)

occ_dfs(1)
finding_level(1 , 1)
assign_levels()

check = set()


for i in range(0, len(occ)):
        if (occ[i] not in check):
                a[occ[i]] = i
                check.add(occ[i])

dfs(1 , 0 , 0 , k)
SegmentTreeConstruction(0, len(occ_by_levels)-1, 0)

q = int(input())
for i in range(0 , q):
    x , y = [int(k) for k in input().split()]
    common_edge = LCA(x,y)
    print(path[x][0]*k + path[y][1]*k - path[common_edge][0]*k - path[common_edge][1]*k)

Time Complexity : O(N(log(N))

7 Likes