PROBLEM LINK:
Author: Full name
Tester: Full name
Editorialist: Oleksandr Kulkov
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Sparse tables, lca
PROBLEM:
You are given undirected graph with N vertices and M edges. If we ignore multiplicity of edges, graph will form a tree. Each edge has some color. You are given Q pairs (u,v). For each pair you should calculate cost of the longest path from u to v where cost is measured as amount of color changes along the path.
QUICK EXPLANATION:
Leave at most 3 colors in each edge. After that use sparse tables like in lca to calculate cost of ascending path with fixed first and last edge. If you have these costs for ascending pathes (u,w) and (v,w), you can easily merge them into costs of path (u,v).
EXPLANATION:
Let’s choose vertex 1 as the root of our tree and erase repeating colors on the same edge. Now we can assume that while answering each query we will first go from u to w=lca(u,v) and then to v.
We should note now that if any edge has multiplicity which exceeds 3, we can assume that it’s equal 3 since that will be enough to choose color which won’t be equal neither preceeding color nor succeeding one in the path, giving maximum possible contribution from this particular edge. Let’s denote d(u,v,l,r) as the maximum cost to go from u to v choosing first edge in the path to be of color l and last edge in the path to be of color r. Here we actually should make l and r be from 1 to 3, i.e. we will use order of color among those possible on first and last edge.
Assume you know d(u,w,l_1,r_1) and d(w,v,l_2,r_2)=d(v,w,r_2,l_2) for every possible l_1,r_1,l_2,r_2. This will give you an opportunity to count maximum possible cost of path from u to v:
Now we reduced the problem to calculating d(u,w,l_1,r_1) and d(v,w,r_2,l_2). Since w is ancestor of poth u and v, we can do it with sparse table (like the ones you use to find lca in the tree). You’ll use quite same formulas as the one above for d(u,v) but will have to make some wrapper so you can iterate through possible colors quickly. This can be done for several ways, for example, you can keep in each vertex array of posssible colors to get from this vertex to its ancestor and also to use some sparse tables to answer level ancestor queries to find vertex preceeding v in ascending path from u to v so you can iterate through possible r easily.
This is quite technical task, please refer to author’s solution for implementation details.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.