P6527 "Wdoi-1" Illusory Energy Collection

Illusory energy is a brand-new kind of energy. **Note: Click "Expand" for a better reading experience.**

In a graph $G=\{V,E\}$, for a vertex set $S\subset V$ of size $C$, if there exists a vertex numbered $v$ such that, taking each vertex in $S$ as a start point and $v$ as the end point, one can choose $C$ paths that do not share multiple edges, then $v$ is called the "focus point" of the set $S$. The map of Gensokyo can be modeled as an edge-weighted unrooted tree with $n$ nodes (the length of a path is defined as the sum of the weights of all edges on the path). The sages have placed illusory energy collectors on $c$ nodes of the tree. To make full use of illusory energy, the sages require that for any subset $S$ of these $c$ nodes with **size at least $2$ and at most a given constant $k$**, an energy hub that is only used to receive illusory energy transmitted by $S$ should be set up at every "focus point" of $S$ in the tree. Let one such "focus point" be $v$. The cost to build this energy hub is computed as follows: $$W_{S,v}=\prod_{u \in S}d(u,v)$$ Here, $d(u,v)$ denotes the shortest distance between the two nodes numbered $u$ and $v$. Since plans may change, the sages have designed **multiple** schemes for placing the $c$ illusory energy collectors, and the constant $k$ corresponding to each scheme is **not necessarily** the same. Now, for each scheme $i$, the sages want to make $q_i$ queries. In each query, they ask: if we only build all the energy hubs that should be built for node $x_{ij}$, what is the total cost (the total cost equals the sum of the costs of building each energy hub)? Since Gensokyo has no computers, they have found you, who are skilled in $\text{OI}$, to help. Of course, since the answer may be very large, you only need to output the result of the total cost $\bmod\ 998244353$.

The first line contains two integers $n,D$, denoting the number of nodes and a certain parameter. The next $n-1$ lines each contain three integers $u,v,w$, denoting an undirected edge between $u$ and $v$ with length $w$. The next line contains an integer $T$, denoting the number of schemes for placing illusory energy collectors. For each scheme: The first line contains two integers $c,k$, denoting the number of illusory energy collectors and the upper bound on the subset size. The second line contains $c$ integers, denoting the $c$ nodes where the collectors are placed. It is guaranteed that these $c$ integers are pairwise distinct. The third line contains an integer $q$, denoting the number of queries for this scheme. The next $q$ lines each contain one integer $x$, denoting a query for the total cost of building all hubs that should be built for node $x$. **For some reason, the actual queried value is $x'=(x-1+D\times lastans)\bmod n+1$**, where $lastans$ denotes the answer to the previous query. For the first query, $lastans=0$. After changing schemes, $lastans$ is **not reset to $0$**.

Output several lines. Each line contains one integer, denoting the answer to the query modulo $\text{998244353}$.

For $100\%$ of the testdata, $1 \le w \le 10^9$, $1 \le u,v,c \le n$, $D\in\{0,1\}$, $2 \le k \le n$. Subtask ID | $n$ | $max(\sum{c_i},\sum{q_i})$ | $T\le$ | Special Constraints | Score :-: | :-: | :-: | :-: | :-: | :-: $1$ | $10$ | $10$ | $10$ | - | $10$ $2$ | $10^4$ | $10^4$ | $1$ | $c=n,k\le 100$ | $15$ $3$ | $10^5$ | $2*10^5$ | $2*10^5$ | $k=2$ | $10$ $4$ | $10^5$ | $2*10^5$ | $2*10^5$ | $D=0,k\le 100$ | $15$ $5$ | $10^5$ | $2*10^5$ | $2*10^5$ | $k \le 100$ | $20$ $6$ | $10^5$ | $2*10^5$ | $2*10^5$ | - | $30$ **This problem uses bundled testing.** Translated by ChatGPT 5