J-Is it a tree?_2026牛客五一集训派对day5

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Students from Antarctic Penguin Language School are counting connected components.

You are given a tree and a cactus with $n$ vertices. The vertices is numbered from $1$ to $n$ .

We define $f(i,j)$ as if we only keep those vertices in the cactus whose number appears on the path from $i$ to $j$ in the tree and the edges between them, how many connected components will be left.

Vertex $1$ is the root. For all $1\leq x\leq n$ , you need to calculate:

$\sum\limits_{i\in S_x}\sum\limits_{j\in S_x,i \leq j}f(i,j)$

in which $S_x$ means the set of vertices in the subtree of vertex $x$ .

A cactus is a simple undirected graph whose nodes are in at most one simple cycle.

输入描述:

The first line contains two integers,  --- the number of nodes and the number of edges in the cactus.

The next  lines, each line contains two integers, describing an edge in the tree.

The next  lines, each line contains two integers, describing an edge in the cactus.

输出描述:

Output  lines, the -th line contains an integer, the answer to .

示例1

输入

复制

输出

复制