No.3194 Do Optimize Your Solution
Note
Problems C and D have the same problem setting and constraints; only the execution time limits differ.
The execution time limit of this problem (Problem D) is 3000 ms.
The execution time limit of this problem is set very strictly. The writer's solution (C++) runs in 950 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 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 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もしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2
tatyam