No.3193 Submit Your Solution
タグ : / 解いたユーザー数 9
作問者 :
noya2
Note
Problems C and D have the same problem setting and constraints, and differ only in the execution time limit.
The execution time limit for this problem (Problem C) is 10000 ms.
Problem Statement
You are given a tree $A$ with $N$ vertices. The vertices of $A$ are numbered $1,2,\dots ,N$, and for $i=1,2,\dots, N-1$, the $i$-th edge connects vertices $u_i,v_i$ of $A$.
Let $d_A(p,q)$ be the distance between $2$ vertices $p,q$ of the tree $A$.
You are also given a tree $B$ with $N$ vertices. The vertices of $B$ are also numbered $1,2,\dots ,N$, and for $j=1,2,\dots, N-1$, the $j$-th edge connects vertices $x_j,y_j$ of $B$.
Let $d_B(p,q)$ be the distance between $2$ vertices $p,q$ of the tree $B$. Find the remainder when $$\sum_{p=1}^{N}\sum_{q=1}^{N}d_A(p,q)d_B(p,q)$$ is divided by $2^{64}$.
Constraints
- $2\le N\le 2\times 10^5$
- $1\le u_i,v_i,x_j,y_j\le N$
- Each of $A,B$ forms a tree with the given edges.
Input
$N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_{N-1}$ $y_{N-1}$
Output
Output the answer on a single line.
Sample
Sample 1
Input
4 1 2 1 3 1 4 1 2 2 3 3 4
Output
28
Sample 2
Input
5 1 2 1 3 2 4 3 5 5 4 4 3 4 2 3 1
Output
68
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。