JERRYTOM:
The result of the game is treewidth + 1.[2]

Hence the problem boils down to computing treewidth of a Chordal Graph.

Note that Treewidth computation is NP complete for general graphs and an FPT algo of it has complexity 2^{k^3}*poly(n) which is no good for practical purposes.

But for chordal graphs this is solvable.

Theorem : Treewidth(G) = min(MaxClique(H) - 1) over all chordal completions of graph G (This is true for any graph and not just chordal graphs).[3]

Since G is a chordal Graph , G is its own chordal completion and hence among all chordal completions , G has the minimum MaxClique size

So now the problem is just to compute the max clique for a chordal graph.

Theorem : Max clique for a chordal graph can be found in linear time.

Proof: A chordal graph has a perfect vertex elimination scheme.[4]
That is , you can order the verteces of the graph as v_1,v_2,...,v_n such that the neighbourhood of v_i in subgraph G[v_i,v_{i+1},...,v_n] is a clique.

This shows that there are atmost O(N) max cliques and each of them can be easily found by going through each node and computing size of its neighbourhood with indices > its own index.

Hence the complexity is pretty much linear , there is also a much simpler method for computing clique of a chordal graph given in [5].

[1].http://logicomp.blogspot.in/2006/05/game-theoretic-characterization-of.html
[2].https://pdfs.semanticscholar.org/820d/d95c833211be602d8da6458e42f6cc72e89f.pdf
[3].https://en.wikipedia.org/wiki/Chordal_completion#Related_graph_families
[4].https://en.wikipedia.org/wiki/Chordal_graph#Perfect_elimination_and_efficient_recognition
[5].https://etd.ohiolink.edu/rws_etd/document/get/kent1208869783/inline


SUBWAY:

consider using 2^k array on tree.
We first let vertex 1 be the root.
Then for every vertex V we precalculate fa[i][V], which is the node that:
1、is V's ancestor.
2、distance between it and V is 2^i. "^" means power here.

For every vertex V and integer tuple {i,x,y}, we calculate dp[V][i][x][y] which is the maximum cost of a path that:
1、starts from V
2、ends at fa[0][fa[i][V]]
3、has the edge between V and fa[0][V] with color x.
4、has the edge betweem fa[i][v] and fa[0][fa[i][v]] with color y.

Now we try to get dp[V][i][x][y] using values dp[V][i-1][x][z] and dp[fa[i-1][V]][i-1][z][y] for all z.
Easy to see that dp[V][i][x][y]=max(for all possible z){dp[V][i-1][x][z]+dp[fa[i-1][V]][i-1][z][y]}.

Easy to see that it will get TLE.

Now we try to improve the calculation of DP.
Let cnt[V] denote the number of different colors on edges betweem V and fa[0][V].
We use (U,V) to denote the edge between U and V on our optimal path.
For some vertex X, when cnt[X]>=3, we can see that: whatever colors other edges have, (X,fa[0][X]) can always take a color that is different from its neighbouring edges on the path.
Thus for every X that cnt[X]>=3, we can imagine that there is only one edge (X,fa[0][X]) with some "magic color" that is different from colors of any other edge (even if another edges also has magic color).
So now cnt[X] drops to 1.

If we do that to all the vertices, cnt[V]<=2 will be satisfied for every vertex V, and the time complexity of DP will drop to O(n log n), because V<=n, i<=log n, x<=2 , y<=2, and z<=2.

Now the problem is to answer query (U,V).
first we divide path U-V into k smaller paths, and each of them has a length that equals some multiplication of 2.
Easy to see that we can achieve k<=2 log n.
Let ans[u][v][x][y] denote the the maximum cost of a path that:
1、starts from u
2、ends at fa[0][v]
3、has the edge between u and fa[0][u] with color x.
4、has the edge betweem v and fa[0][v] with color y.
And for paths u-v and v-w we have:
ans[u][w][x][y]=max(for all possible z){ans[u][v][x][z]+ans[v][w][z][y]}
In this way we can merge two neighbouring paths among the k ones.
By doing this k-1 times we get the answer of the whole path, ans[U][V][x][y].

Total complexity: O((n+q) log n).
PDELIV:
We can reduce this problem to the following: given n linear functions f_i(x) and O(m + sum k_i) queries of the following format:
l, r, x -- find max(f_l(x), f_{l + 1}(x), ..., f_r(x))
It's so because when we deny to buy pizza from k pizzerias, the others are divided to at most k + 1 segments.

To answer such queries we can build a segment tree, where in each node we will store a convex hull of the functions corresponding to the segment.

Building the segment tree: O(n log n). Answering the queries can be done in O((n + m + sum k_i) log n) by processing them offline.

O(n * sqrt(n)) passes, too. (sqrt decomposition instead of segment tree)

PFRUIT (pdf/download): https://dropmefiles.com/jZUUD