F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

树论(一)

Time Limit: 16000/8000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1259    Accepted Submission(s): 335


Problem Description
一天,学傻了的Yoshinow在学数论时,迷失在了数论的黑暗森林里!

(因为是在数论森林里!)现在Yoshinow得到了一棵树,现在他想知道:在某个以 $ r $ 为根的子树内,有多少点对 $ (i,j) $ ,满足 $ i,j $ 的最小公倍数不超过 $ x $(注意是**编号**的lcm)

由于Yoshinow非常——好奇,所以他现在一共有 $ Q $ 个这样的询问。

**形式化地说:**给定 $ n $ 个结点的有根树(以 $ 1 $ 为根),结点标号从 $ 1 $ 到 $ n $ ,共有 $ Q $ 次询问,每次询问给出两个参数 $r,x$ ,表示询问有多少点对 $(i,j)$,满足:

- 1、$i,j$ 是 $ [1,n] $ 内的正整数。
- 2、$ lcm(i,j)\leq x $.
- 3、标号为 $i,j$ 的结点均在以 $r$ 为根的子树内。


注:对于正整数$ x,y $, $ lcm(x,y) $ 表示 $ x,y $ 的最小公倍数,即同时是 $ x,y $ 倍数的最小正整数。例如,$ 10 $ 和 $ 12 $ 的最小公倍数是 $ 60 $,即 $ lcm(10,12)=60 $.
 

Input
第一行输入一个正整数 $T$,表示测试用例组数,$ 1\leq T\leq 3 $.

对每组询问:第一行输入一个整数$n$,其中$ 1\leq n\leq 10^5 $。

接下来 $n-1$ 行,每行两个整数 $ u,v(1\leq u,v\leq n) $,表示 $u,v$ 之间有一条边。保证给出的 $n$ 个点构成树。

接下来一行一个整数$Q$,表示询问组数,$ 1\leq Q\leq 10^6 $.

接下来 $Q$ 行,每行两个整数 $ r,x(1\leq r\leq n,0\leq x\leq 10^5) $,表示一个询问。
 

Output
共 $T$ 行,对每组测试用例,输出一行共 $Q$ 个整数,按顺序给出对应询问的答案,相邻整数用空格隔开。
 

Sample Input
1 7 1 3 1 7 3 2 3 5 5 4 5 6 5 3 23 5 10 5 30 1 5 1 7
 

Sample Output
23 3 9 15 27
 

Hint

样例给出的树如图所示:

对于第一个询问,$r=3,x=23$,$r=3$ 的子树内共有 $5$ 个点,有 $5^2=25$ 对点对,除了 $(5,6),(6,5)$ 的最小公倍数是 $30>23$ 外,其余每个点对都满足最小公倍数不超过 $23$ 的条件,因此答案是 $25-2=23$.
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-11-10 07:57:26, Gzip enabled