LazerTree

F. LazerTree

Problem Statement

LHS is under siege: There are imposters among us! Abstractly, LHS can be visualized as a tree with $$N$$ nodes. Moreover, since imposters like to band together, they are always along a simple path, described by two endpoints $$(u,v)$$. Fortunately, Jason was able to intercept the imposters' communication and identify a list of $$Q$$ potential paths that might have been infiltrated. In addition, LHS has long been ready for such an imposter attack, and has installed lazer emitters at every node. A lazer beam is also described by a simple path between endpoints $$(u,v)$$. A configuration of $$n$$ lazers is considered successful if the intersection(edges present in both simple paths) between any pair of lazer paths is exactly the path $$(u,v)$$ that the imposters are on (no more and no less because you want neither to harm the innocent nor leave any imposters alive). Being the curious contestant you are, you decide to count the number of successful configurations for each path on the potential list. For each potential path where the imposters lie on $$(u,v)$$, there is a limited number of $$k$$ lazer beams available, so you want to calculate the number of successful configurations using exactly $$k$$ lazer beams. Since the number can get quite large, calculate its modulo equivalence under $$998244353$$.

More formally, you are given a tree with $$N$$ nodes and $$Q$$ queries. Each query has $$3$$ numbers: $$u$$, $$v$$, and $$k$$. You have to find the number of ways to pick exactly $$k$$ simple paths on the tree such that the intersection of any two of them is exactly the simple path between nodes $$(u,v)$$. Note that order does matter, i.e. $$\{(1,4), (2,5)\}$$ is different from $$\{(2,5),(1,4)\}$$, and the paths aren't necessarily distinct and may share endpoints. Output the number of ways modulo $$998244353$$ for each query.

Time Limit:
C++: 2.5 seconds
Java, Python: 5 seconds
Memory Limit: 256mb

Constraints

$$1 \leq N,Q \leq 10^5$$ and $$2 \leq k \leq min(500,N)$$
Additionally, it is guarenteed that each node's degree is less than or equal to $$500$$.

Input format

The first line contains four integers, $$N$$, $$Q$$
The following $$N - 1$$ lines each describe an edge $$(u,v)$$
The last $$Q$$ lines each describe a query with 3 integers: $$u$$, $$v$$, $$u \neq v$$, and $$k$$.

Output format

Output $$Q$$ lines of integers, with the $$i$$th line being the answer to the $$i$$th query.

5 3
1 2
1 3
2 4
2 5
1 4 2
3 5 3
1 2 2

3
1
21

Sample Explanation

For the first query, there are $$3$$ successful configurations: $$\{(1,4),(1,4)\}$$, $$\{(1,4),(3,4)\}$$, and $$\{(3,4),(1,4)\}$$.
For the second query, there is only $$1$$ successful configuration: $$\{(3,5),(3,5),(3,5)\}$$