#2564. 「SDOI2018」原题识别

内存限制:512 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: zjq

题目描述

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

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

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

  • 1 x y:如果将 xxx 点到 yyy 点的最短路径上的所有点(包括 xxxyyy)对应的题目都做一遍,那么一共可以做到多少道本质不同的题目?
  • 2 A B:如果在 AAA 点到根的最短路径上(包括AAA点和根)等概率随机选择一个点xxx,在 BBB 点到根的最短路径上(包括 BBB 点和根)等概率随机选择一个点 yyy,那么询问 1 x y 的答案期望是多少?

定义 cntxcnt_xcntx 表示 xxx 点到根最短路径上的节点个数,因为小Q不喜欢分数,而且第2类询问的答案一定可以表示成 anscntA×cntB\frac{ans}{cnt_A\times cnt_B}cntA×cntBans的形式,你只需要告诉他 ansansans 的值就可以了。

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

输入格式

第一行包含一个正整数 TTT,表示测试数据的组数。

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

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

如对生成方式仍有疑问,请参考下发文件中的参考程序。

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

接下来 mmm 行,每行 333 个正整数,形式为 1 x y 或者 2 A B,依次表示每个询问。

输出格式

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

样例

样例输入 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

样例 2

见下发文件。

数据范围与提示

1≤T≤3,2≤p≤n≤100000,1≤m≤200000,10000≤SA,SB,SC≤1000000,1≤x,y,A,B≤n1\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 n1T3,2pn100000,1m200000,10000SA,SB,SC1000000,1x,y,A,Bn

子任务1(30分):只含第1类询问。
子任务2(30分):满足 p=np=np=n
子任务3(40分):没有任何附加的限制。