#P3488. [ONTAK2010]Highways

    ID: 2701 传统题 1000ms 512MiB 尝试: 330 已通过: 43 难度: 7 上传者: 标签>难度分类提高+/省选-树算法子树转区间树上倍增构造与建模补集转化组合数学容斥原理离线与分治离线查询计算几何扫描线数据结构树状数组CF2200

[ONTAK2010]Highways

Highways

题目描述

Byteland 有 NN 座城市,由 N−1N-1 条双向普通道路连通。只使用普通道路时,两座城市之间有且只有一条简单路线,称为它们之间的主路线。为了缓解交通拥堵,Byteland 还修建了一些双向高速公路。

每条路线都是一串相连的道路,沿途的城市不能重复。从城市 xx 到城市 yy 可以走主路线,也可以走一条恰好使用一条高速公路的路线。后一种路线与主路线只能在两端的城市 x,yx,y 相交,中途不能经过主路线上的任何城市。

对每对给定的城市,求可以采用的路线总数,主路线也算一种。

输入格式

第一行包含一个整数 NN。城市编号从 11 到 NN。

接下来 N−1N-1 行,每行两个整数 Ai,BiA_i,B_i,表示一条普通道路的两个端点。

接下来一行是高速公路数 MM,其后 MM 行分别给出一条高速公路的两个端点。

再接下来一行是询问数 QQ,其后 QQ 行分别给出一次询问的起点 xx 和终点 yy。

输出格式

输出 QQ 行,第 ii 行是第 ii 次询问的路线数。

样例 #1

9
1 2
2 3
4 2
1 5
5 6
7 5
7 8
9 7
4
2 5
3 4
6 4
8 3
4
4 9
2 5
1 6
1 7
1
4
2
2

数据范围

1≤N,M≤1051\le N,M\le 10^5,1≤Q≤5×1051\le Q\le 5\times10^5。所有城市编号在 11 到 NN 之间。每条公路的两个端点不同,每次询问的起点和终点也不同。