infoarena informatica de performanta

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

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

\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
1 2 1
2 3 100
1 2
2 3
1 3
}{
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}