308234: CF1486F. Pairs of Paths

Memory Limit:512 MB Time Limit:6 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Pairs of Paths

题意翻译

给定一棵包含 $n$ 个节点(编号 $1$ 到 $n$),$n-1$ 条边(编号 $1$ 到 $n-1$)的树,我们同时选定该树上的 $m$ 条简单路径 $path_1,path_2,...,path_m$。第 $i$ 条边连接节点 $u_i,v_i$,第 $i$ 条简单路径 $path_i$ 为节点 $x_i,y_i$ 之间的最短路径。 你需要找出对于这棵树,有多少个二元组 $(i,j)$ 满足: - $1\leq i,j\leq m$ 且 $i\ne j$。 - $path_i$ 和 $path_j$ 有且仅有一个交点。 第一行输入一个整数 $n$,接下来输入 $n-1$ 行,第 $i$ 行两个整数表示 $u_i,v_i$;然后输入一行一个整数 $m$,最后输入 $m$ 行,第 $i$ 行两个整数表示 $x_i,y_i$。 输出有多少满足要求的二元组。 $1\leq n,m\leq3\times10^5;1\leq u_i,v_i,x_i,y_i\leq n;$ 样例解释: 对于样例一: ![](https://cdn.luogu.com.cn/upload/image_hosting/uvhwvz3s.png) 满足要求的二元组为 $(1,4),(3,4)$。 对于样例三: ![](https://cdn.luogu.com.cn/upload/image_hosting/prqo45wk.png) 满足要求的二元组为 $(1,4),(3,4),(1,5),(2,5),(3,5),(3,6),(5,6)$。

题目描述

You are given a tree consisting of $ n $ vertices, and $ m $ simple vertex paths. Your task is to find how many pairs of those paths intersect at exactly one vertex. More formally you have to find the number of pairs $ (i, j) $ $ (1 \leq i < j \leq m) $ such that $ path_i $ and $ path_j $ have exactly one vertex in common.

输入输出格式

输入格式


First line contains a single integer $ n $ $ (1 \leq n \leq 3 \cdot 10^5) $ . Next $ n - 1 $ lines describe the tree. Each line contains two integers $ u $ and $ v $ $ (1 \leq u, v \leq n) $ describing an edge between vertices $ u $ and $ v $ . Next line contains a single integer $ m $ $ (1 \leq m \leq 3 \cdot 10^5) $ . Next $ m $ lines describe paths. Each line describes a path by it's two endpoints $ u $ and $ v $ $ (1 \leq u, v \leq n) $ . The given path is all the vertices on the shortest path from $ u $ to $ v $ (including $ u $ and $ v $ ).

输出格式


Output a single integer — the number of pairs of paths that intersect at exactly one vertex.

输入输出样例

输入样例 #1

5
1 2
1 3
1 4
3 5
4
2 3
2 4
3 4
3 5

输出样例 #1

2

输入样例 #2

1
3
1 1
1 1
1 1

输出样例 #2

3

输入样例 #3

5
1 2
1 3
1 4
3 5
6
2 3
2 4
3 4
3 5
1 1
1 2

输出样例 #3

7

说明

![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1486F/a19cd21d095785ac889753153b27201ab276d741.png) The tree in the first example and paths look like this. Pairs $ (1,4) $ and $ (3,4) $ intersect at one vertex. In the second example all three paths contain the same single vertex, so all pairs $ (1, 2) $ , $ (1, 3) $ and $ (2, 3) $ intersect at one vertex. The third example is the same as the first example with two additional paths. Pairs $ (1,4) $ , $ (1,5) $ , $ (2,5) $ , $ (3,4) $ , $ (3,5) $ , $ (3,6) $ and $ (5,6) $ intersect at one vertex.

Input

题意翻译

给定一棵包含 $n$ 个节点(编号 $1$ 到 $n$),$n-1$ 条边(编号 $1$ 到 $n-1$)的树,我们同时选定该树上的 $m$ 条简单路径 $path_1,path_2,...,path_m$。第 $i$ 条边连接节点 $u_i,v_i$,第 $i$ 条简单路径 $path_i$ 为节点 $x_i,y_i$ 之间的最短路径。 你需要找出对于这棵树,有多少个二元组 $(i,j)$ 满足: - $1\leq i,j\leq m$ 且 $i\ne j$。 - $path_i$ 和 $path_j$ 有且仅有一个交点。 第一行输入一个整数 $n$,接下来输入 $n-1$ 行,第 $i$ 行两个整数表示 $u_i,v_i$;然后输入一行一个整数 $m$,最后输入 $m$ 行,第 $i$ 行两个整数表示 $x_i,y_i$。 输出有多少满足要求的二元组。 $1\leq n,m\leq3\times10^5;1\leq u_i,v_i,x_i,y_i\leq n;$ 样例解释: 对于样例一: ![](https://cdn.luogu.com.cn/upload/image_hosting/uvhwvz3s.png) 满足要求的二元组为 $(1,4),(3,4)$。 对于样例三: ![](https://cdn.luogu.com.cn/upload/image_hosting/prqo45wk.png) 满足要求的二元组为 $(1,4),(3,4),(1,5),(2,5),(3,5),(3,6),(5,6)$。

加入题单

上一题 下一题 算法标签: