F. 比赛

题目描述

小 N 和小 O 会在 2022 年 11 月参加一场盛大的程序设计大赛 NOIP！小 N 和小 O 各自率领了一支 $n$ 个人的队伍。

由于组委会玩原神，它们由世界树汲取灵感，玩出了一棵 $n$ 个点的树 $G$。

称一条树边 $(u,v)$ 关于区间 $[l,r]$ 是好的，当且仅当存在 $l\leq i<j\leq r$，使得编号为 $i,j$ 的点在树上的简单路径经过了 $(u,v)$。

每场比赛前，考虑到路途距离，选手连续参加比赛等因素，小 P 会选择两个参数 $l, r$（$1 \leq l \leq r \leq n$），表示这一场比赛会邀请两队中编号属于 $[l, r]$ 的所有选手来到现场准备比赛。在比赛现场，小 N 和小 O 会以掷骰子的方式挑选出参数 $p, q$（$l \leq p \leq q \leq r$），只有编号属于 $[p, q]$ 的选手才能参赛。此时，这个区间 $[p,q]$ 产生的精彩程度为关于 $[p,q]$ 好的树边数量。

NOIP 总共有 $Q$ 场比赛，每场比赛的参数 $l, r$ 都已经确定，但是 $p, q$ 还没有抽取。小 P 想知道，对于每一场比赛，在其所有可能的 $p, q$（$l \leq p \leq q \leq r$）参数下的比赛的精彩程度之和。由于答案可能非常之大，你只需要对每一场答案输出结果对 $2 ^ {64}$ 取模的结果即可。

输入格式

第一行一个正整数 $n$。

接下来 $n-1$ 行，每行包含两个正整数 $u,v$，代表一条树边 $(u,v)$。

接下来一行一个正整数 $Q$。

接下来 $Q$ 行，每行包含两个正整数 $l,r$，代表一次询问。

输出格式

输出 $Q$ 行，第 $i$ 行包含一个非负整数，表示第 $i$ 场比赛中所有可能的比赛的精彩程度之和对 $2 ^ {64}$ 取模的结果。

样例 #1

样例输入 #1

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

样例输出 #1

7
7
3
42
1
27

数据范围

对于 $100\%$ 的数据，满足 $1\le n,q\le 5\times 10^4,1\le u,v\le n,1\le l\le r\le n$。

特殊性质 $A$：保证给定的树是一条链。

• Subtask 1（20 pts）：$n,q\leq 50$。
• Subtask 2（20 pts）：$n,q\leq 5000$ 且满足特殊性质 A。
• Subtask 3（25 pts）：$n,q\leq 5000$。
• Subtask 4（35 pts）：$n,q\leq 5\times 10^4$。