#F. [CZOJ 一周一测 R10 F] 比赛

    传统题 3000~4000ms 512MiB

[CZOJ 一周一测 R10 F] 比赛

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

F. 比赛

题目描述

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

由于组委会玩原神,它们由世界树汲取灵感,玩出了一棵 nn 个点的树 GG

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

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

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

输入格式

第一行一个正整数 nn

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

接下来一行一个正整数 QQ

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

输出格式

输出 QQ 行,第 ii 行包含一个非负整数,表示第 ii 场比赛中所有可能的比赛的精彩程度之和对 2642 ^ {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%100\% 的数据,满足 $1\le n,q\le 5\times 10^4,1\le u,v\le n,1\le l\le r\le n$。

特殊性质 AA:保证给定的树是一条链。

  • Subtask 1(20 pts):n,q50n,q\leq 50
  • Subtask 2(20 pts):n,q5000n,q\leq 5000 且满足特殊性质 A。
  • Subtask 3(25 pts):n,q5000n,q\leq 5000
  • Subtask 4(35 pts):n,q5×104n,q\leq 5\times 10^4

[CZR-010] CZOJ Weekly Exercise Round 10

未参加
状态
已结束
规则
IOI
题目
6
开始于
2024-5-3 17:00
结束于
2024-5-3 22:00
持续时间
5 小时
主持人
参赛人数
12