原题识别
测试数据来自 system/2048
描述
"人肉题库" 小Q刷题非常勤奋,题量破万。每当有人拿题目请教他时,小Q总能在1秒内报出这是哪个OJ的哪道题。因此,小Q是被当作 "原题搜索机" 一样的存在。
有一天,小Q来到了一棵\(n\)个节点的有根树下,这棵树的根节点为1号点,且每个节点都印着一道题目。凭借超大的题量,小Q迅速识别出了每道题的来源,并发现有些题目被搬运了好多次。他把每个节点的题目都做了一个分类,第\(i\)个节点的题目对应的题目种类为\(a_i\),当且仅当\(a_i=a_j\)时,\(i\)点和\(j\)点的题目来源是相同的。
同一道题目做多次除了增加AC数以外,对本身的水平没有任何提高。为了调查这棵树的题目质量,小Q会不断提出以下两种询问共\(m\)次:
- 1 \(x\) \(y\):如果将\(x\)点到\(y\)点的最短路径上的所有点(包括\(x\)和\(y\))对应的题目都做一遍,那么一共可以做到多少道本质不同的题目?
- 2 \(A\) \(B\):如果在\(A\)点到根的最短路径上(包括\(A\)点和根)等概率随机选择一个点\(x\),在\(B\)点到根的最短路径上(包括\(B\)点和根)等概率随机选择一个点\(y\),那么询问1 \(x\) \(y\)的答案期望是多少?
定义\(cnt_x\)表示\(x\)点到根最短路径上的节点个数,因为小Q不喜欢分数,而且第2类询问的答案一定可以表示成\(\frac{ans}{cnt_A\times cnt_B}\)的形式,你只需要告诉他\(ans\)的值就可以了。
识别这些题目消耗了小Q太大的精力,他没有办法自己去计算这些简单的询问的答案。请写一个程序回答小Q的所有\(m\)个问题。
格式
输入格式
第一行包含一个正整数\(T\),表示测试数据的组数。
每组数据第一行包含5个正整数\(n,p,SA,SB,SC\),其中\(n\)表示树的节点个数。
为了在某种程度上减少输入量,树边和每个点的题目种类\(a[]\)将由以下代码生成:
unsigned int SA, SB, SC;
unsigned int rng61(){
SA ^= SA << 16;
SA ^= SA >> 5;
SA ^= SA << 1;
unsigned int t = SA;
SA = SB;
SB = SC;
SC ^= t ^ SA;
return SC;
}
void gen(){
scanf("%d%d%u%u%u", &n, &p, &SA, &SB, &SC);
for(int i = 2; i <= p; i++)
addedge(i - 1, i);
for(int i = p + 1; i <= n; i++)
addedge(rng61() % (i - 1) + 1, i);
for(int i = 1; i <= n; i++)
a[i] = rng61() % n + 1;
}
第二行包含一个正整数\(m\),表示询问次数。
接下来\(m\)行,每行3个正整数,形式为1 \(x\) \(y\)或者2 \(A\) \(B\),依次表示每个询问。
输出格式
对于每组数据,输出\(m\)行,每行一个整数,依次回答每个询问。
样例1
样例输入1
2
5 3 10000 12345 54321
3
1 2 3
2 1 3
1 3 2
10 6 23456 77777 55555
5
1 1 10
2 3 5
2 7 5
2 5 4
1 8 6
样例输出1
1
5
1
4
34
61
45
3
限制
\(1\le T\le 3\),\(2\le p\le n\le 100000\),\(1\le m\le 200000\),
\(10000\le SA,SB,SC\le 1000000\),\(1\le x,y,A,B\le n\)。
子任务1(30分):只含第1类询问。
子任务2(30分):满足 \(p=n\)。
子任务3(40分):没有任何附加的限制。
来源
SDOI 2018 Round2
信息
- ID
- 1980
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者