\documentclass[11pt,a4paper,oneside]{article}
\usepackage[utf8]{inputenc}

== include(page="template/taskheader" task_id="arbquery") ==

\usepackage{fancyhdr}
\usepackage[romanian]{babel}

Manuela are un arbore cu $N$ noduri, unde fiecare muchie are câte o lungime. Un lanţ este o secvenţă de noduri distincte <tex> $x_1, ..., x_k$ </tex>, astfel încât să existe câte o muchie între oricare două noduri adiacente. Numim lungimea unui lanţ <tex> x_1, ..., x_k </tex> suma lungimilor muchiilor care unesc nodurile adiacente din drum. Pentru fiecare muchie $(x, y)$ fie $d(x, y)$ suma lungimilor tuturor lanţurilor care conţin muchia de la $x$ la $y$.

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{listings}
\usepackage{amssymb}
\usepackage{color}
\usepackage{mysty}
 
\begin{document}
 
\myheader{Arb Query}{arbquery.in}{arbquery.out}
 
Manuela are un arbore cu $N$ noduri, unde fiecare muchie are câte o lungime. Un lanţ este o secvenţă de noduri distincte $x_1, \ldots, x_k$, astfel încât să existe câte o muchie între oricare două noduri adiacente. Numim lungimea unui lanţ $x_1, \ldots, x_k$ suma lungimilor muchiilor care unesc nodurile adiacente din drum. Pentru fiecare muchie $(x, y)$ fie $d(x, y)$ suma lungimilor tuturor lanţurilor care conţin muchia de la $x$ la $y$.
 
Manuela are $Q$ interogări, fiecare de forma unui lanţ $x_1, \ldots, x_k$. Ea vrea să afle suma $d(x_1, x_2) + \ldots + d(x_{k-1}, x_k) \mod 10^9 + 7$.
 
\mysection{Date de intrare}
 
Primul rând al fişierului de intrare conţine numărele $N$ şi $Q$. Urmează $N - 1$ rânduri, fiecare conţinând trei valori $x, y, l$, ce indică existenţa unei muchii de la $x$ la $y$ cu lungimea $l$. Urmează apoi $Q$ linii, fiecare conţinând două valori $x, y$, ce reprezintă o interogare asupra lanţului unic de la $x$ la $y$.
 
\mysection{Date de ieşire}
 
Fişierul de ieşire conţine răspunsurile celor $Q$ interogări, în ordine.
 
\mysection{Subtaskuri}
\mysubsection{Subtask 1 (10 puncte)}
\begin{itemize}
\item $N, Q \leq 20$.
\item Oricare muchie are lungimea cel mult $10^5$.
\end{itemize}
 
\mysubsection{Subtask 2 (30 puncte)}
\begin{itemize}
\item $N, Q \leq 2.000$.
\item Oricare muchie are lungimea cel mult $10^5$.
\end{itemize}
 
\mysubsection{Subtask 3 (10 puncte)}
\begin{itemize}
\item $N, Q \leq 100.000$.
\item Oricare nod are cel mult 2 muchii incidente.
\item Oricare muchie are lungimea cel mult $10^5$.
\end{itemize}
 
\mysubsection{Subtask 4 (10 puncte)}
\begin{itemize}
\item $N, Q \leq 100.000$.
\item Cel mult un nod are mai mult de 1 muchie incidentă.
\item Oricare muchie are lungimea cel mult $10^5$.
\end{itemize}
 
\mysubsection{Subtask 5 (40 puncte)}
\begin{itemize}
\item $N, Q \leq 100.000$.
\item Oricare muchie are lungimea cel mult $10^5$.
\end{itemize}
 
\begin{examples}{Exemple}{arbquery.in}{arbquery.out}
\exmp{
3 3

Manuela are $Q$ interogări, fiecare de forma unui lanţ <tex> x_1, ..., x_k </tex>. Ea vrea să afle suma <tex> d(x_1, x_2) + ... + d(x_{k-1}, x_k) </tex> % 10^9^+ 7.
 
h2. Date de intrare
 
Primul rând al fişierului de intrare $arbquery.out$ conţine numărele $N$ şi $Q$. Urmează $N - 1$ rânduri, fiecare conţinând trei valori $x, y, l$, ce indică existenţa unei muchii de la $x$ la $y$ cu lungimea $l$. Urmează apoi $Q$ linii, fiecare conţinând două valori $x, y$, ce reprezintă o interogare asupra lanţului unic de la $x$ la $y$.
 
h2. Date de ieşire
 
Fişierul de ieşire $arbquery.out$ conţine răspunsurile celor $Q$ interogări, în ordine.
 
h2. Subtaskuri
 
* *Subtask 1 (10 puncte)*
** $N, Q ≤ 20$.
** Oricare muchie are lungimea cel mult $10^5^$.
 
* *Subtask 2 (30 puncte)*
** $N, Q ≤ 2.000$.
** Oricare muchie are lungimea cel mult $10^5^$.
 
* *Subtask 3 (10 puncte)*
** $N, Q ≤ 100.000$.
** Oricare nod are cel mult 2 muchii incidente.
** Oricare muchie are lungimea cel mult $10^5^$.
 
* *Subtask 4 (10 puncte)*
** $N, Q ≤ 100.000$.
** Cel mult un nod are mai mult de 1 muchie incidentă.
** Oricare muchie are lungimea cel mult $10^5^$.
 
* *Subtask 5 (40 puncte)*
** $N, Q ≤ 100.000$.
** Oricare muchie are lungimea cel mult $10^5^$.
 
h2. Exemplu
 
table(example). |_. arbquery.in |_. arbquery.out |
| 3 3

1 2 1
2 3 100
1 2
2 3
1 3

}{
102

| 102

201
303

}%
\end{examples}
 
\mysubsection{Explicaţie}

|

Observăm că sunt trei lanţuri, $1 - 2$ de cost 1, $2 - 3$ de cost $100$ şi $1 - 2 - 3$ de cost $101$. Astfel $d(1, 2) = 102, d(2, 3) = 201$. Astfel rezultatul pentru $1, 2$ este $d(1, 2) = 102$, pentru $2, 3$ este $d(2, 3) = 201$, şi pentru $1, 3$ este $d(1, 2) + d(2, 3) = 303$.

\end{document}
 

== include(page="template/taskfooter" task_id="arbquery") ==