問題一覧 > 通常問題

No.3194 Do Optimize Your Solution

レベル : / AI推定難易度 : 2900 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 10
作問者 : noya2 / テスター : tatyam
お気に入りにしたユーザー ProblemId : 12416 / 自分の提出
問題文最終更新日: 2025-06-27 21:19:02
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 472 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。