#P4618. [SDOI2018] 原题识别

    ID: 4997 远端评测题 10000ms 500MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2018各省省选山东O2优化枚举,暴力主席树

[SDOI2018] 原题识别

题目背景

  • Input file: old.in
  • Output file: old.out
  • Time limit: 10 seconds
  • Memory limit: 512 megabytes

题目描述

“人肉题库” 小 QQ 刷题非常勤奋,题量破万。每当有人拿题目请教他时,小 QQ 总能在 11 秒内报出这 是哪个 OJOJ 的哪道题。因此,小 QQ 是被当作 “原题搜索机” 一样的存在。

有一天,小 QQ 来到了一棵 nn 个节点的有根树下,这棵树的根节点为 11 号点,且每个节点都印着一道 题目。凭借超大的题量,小 QQ 迅速识别出了每道题的来源,并发现有些题目被搬运了好多次。他把每个 节点的题目都做了一个分类,第 ii 个节点的题目对应的题目种类为 aia_i,当且仅当 ai=aja_i=a_j 时,ii 点和 jj 点的题目来源是相同的。

同一道题目做多次除了增加 ACAC 数以外,对本身的水平没有任何提高。为了调查这棵树的题目质量, 小 QQ 会不断提出以下两种询问共 mm 次:

  • 11 xx yy:如果将 xx 点到 yy 点的最短路径上的所有点 (包括 xxyy) 对应的题目都做一遍,那么一共可 以做到多少道本质不同的题目?

  • 22 AA BB:如果在 AA 点到根的最短路径上 (包括 AA 点和根) 等概率随机选择一个点 xx,在 BB 点到根的最短路径上 (包括 BB 点和根) 等概率随机选择一个点 yy,那么询问 11 xx yy 的答案期望是多少?

定义 cntxcnt_x 表示 xx 点到根最短路径上的节点个数,因为小 QQ 不喜欢分数,而且第 22 类询问的答案一 定可以表示成anscntAcntB\frac{ans}{{cnt_A}*{cnt_B}}的形式,你只需要告诉他 ansans 的值就可以了。

识别这些题目消耗了小 QQ 太大的精力,他没有办法自己去计算这些简单的询问的答案。请写一个程序回答小 QQ 的所有 mm 个问题。

输入格式

第一行包含一个正整数 TT,表示测试数据的组数。 每组数据第一行包含 55 个正整数 n,p,SA,SB,SCn, p, SA, SB, SC,其中 nn 表示树的节点个数。

为了在某种程度上减少输入量,树边和每个点的题目种类 a[]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;
}

第二行包含一个正整数 mm,表示询问次数。

接下来 mm 行,每行 33 个正整数,形式为 11 xx yy 或者 22 AA BB,依次表示每个询问。

输出格式

对于每组数据,输出 mm 行,每行一个整数,依次回答每个询问。

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
5
1
4
34
61
45
3

提示

-1T3,2pn100000,1m2000001 ≤ T ≤ 3,2 ≤ p ≤ n ≤ 100000,1 ≤ m ≤ 200000 -10000SA,SB,SC1000000,1x,y,A,Bn 10000 ≤ SA, SB, SC ≤ 1000000,1 ≤ x, y, A, B ≤ n

子任务 113030 分):只含第 11 类询问。

子任务 223030 分):满足 p=np = n

子任务 334040 分):没有任何附加的限制。