题目描述

给定一颗节点编号为1~n的，且以1为根的树，给出n组询问，每次询问给定一个数对(x,y)，求i为x到根路径上的点(包括x和根) (y+2i)xor(y+i)，对于这n组询问的答案，不需要依次输出n个数，你只需要输出他们的和对998244353的取模即可。
树的信息以及询问不会直接给出，输入数据只包含随机种子，具体生成方式请仔细阅读备注内容。
示例1
输入：3,1,1,1,1
返回值：7
备注：
输入数据包含5个整数，n,seed1,seed2,seed3,x.
树的信息生成伪代码如下
//////////////////////1/////////////////////
定义边集数组u[],v[] //u[i],v[i]表示第i条边的两个端点
定义变量seed4
定义循环变量i从1到n-1
循环体开始
seed4=(seed1+seed2)%998244353*seed3%998244353;
u[i]=i+1;
v[i]=(seed4%i)+1;
seed3=seed2;
seed2=seed1;
seed1=seed4;
循环体结束
//////////////////////1/////////////////////
询问信息生成伪代码如下，顺带一提，第一次询问的x会在输入中给出
//////////////////////2/////////////////////
定义变量lastans，初始值为0
定义变量ret，初始值为0
定义变量y，初始值为0 //含义见题干
定义函数ans(x,y)，返回值为对数对(x,y)这组询问的答案 //这里“询问”的含义见题干
定义变量z
定义循环变量i从1到n
循环体开始
z=ans(x,y);
ret=(ret+z)%998244353;
lastans=z;
x=((x+lastans)^ret)%n+1;
y=lastans;
循环体结束
//////////////////////2/////////////////////
输出一个整数，表示答案。
n<=10^5,seed1,seed2,seed3<=10^9,x<=n
保证构造出的数据合法。

题目分析

题目主要给出的信息有三个：
1.根据随机给出的种子信息，会生成树的信息，主要是边集数组u[i]和v[i]；
2.定义了n组询问(x, y)，每组询问y都是上一组询问的结果；
3.定义了ans(x,y)，对询问进行结果计算的方式，从x到根节点的特殊计算；
生成树的信息和进行n组询问都给出了具体过程代码，而对询问结果的计算需要在确定树的信息后才能进行计算，在这里做了一个特殊处理，将边集数组转化为一个子节点的父节点信息，所有的子节点最终的父节点都是根节点。
在定义边集数组中有：u[i]=i+1; v[i]=(seed4%i)+1; （u[i],v[i]表示第i条边的两个端点）
一条边的一个端点是 u[i]（=i+1），则将这个端点作为一条边的是它的父节点 v[u[i]] 是 u[i]的父节点，最后转换为 parent[u[i]] = v[i]（parent[i+1] = v[i]）；
可以根据这个数组，从x的 parent[x]一直访问到根节点1，从而方便计算结果。

解题思路

方法1：根据边集数组，生成树结点的父子节点之间的关系，在循环中求从x到根节点的计算结果，最后将每一组询问的结果相加取模
1.定义一个长度为n+1的parent数组，来保存结点的父节点信息，根节点为1；
2.根据随机种子，生成树的信息；
3.y从0开始，进行询问，将上次询问结果作为y，进行下一次询问，同时使用一个ret记录每次询问结果的和；
4.在询问结果的计算过程中，不断从x开始向根节点计算，直到父节点是根节点；

代码实现

Java实现

    long[] parent;
    int mod = 998244353;
    public long work (int n, long seed1, long seed2, long seed3, int x) {
        parent = new long[n+1];
        // 生成树的信息，确定每个结点的父结点
        for(int i=1;i<n;i++){
            long seed4 = (seed1 + seed2) % mod * seed3 % mod;
            parent[i+1] = (seed4 % i) +1;
            seed3 = seed2;
            seed2 = seed1;
            seed1 = seed4;
        }
        long ret = 0;
        long lastans = 0;
        int y = 0;
        // 生成n组询问
        for(int i=1;i<=n;i++){
            // 获取每次询问的结果
            long z = ans(x, y);
            // 将询问结果相加取模
            ret = (ret + z) % mod;
            lastans = z;
            x = (int) ((x+lastans)^ret)%n + 1;
            y = (int) lastans;
        }
        return ret;
    }

    // 生成询问结果
    long ans(int x, int y){
        long a = 0;
        int i = x;
        // 从x往根节点计算
        while(i != 1){
            a += (y + 2*i) ^ (y+i);
            i = (int)parent[i];
        } 
        a += (y + 2) ^ (y + 1);
        return a;
    }

时间复杂度：，首先需要n次循环生成树的父节点信息，然后在n次的询问过程中，需要进行最多n次的循环计算到根节点，所以时间复杂度为；
空间复杂度：，需要额外n+1的空间来存储树结点的信息；

C++实现

    vector<int> parent;
    int mod = 998244353;
    long long work(int n, long long seed1, long long seed2, long long seed3, int x) {
        parent.resize(n+1,0);
        // 生成树的信息，确定每个结点的父结点
        for(int i=1;i<n;i++){
            long long seed4 = (seed1 + seed2) % mod * seed3 % mod;
            parent[i+1] = (seed4 % i) +1;
            seed3 = seed2;
            seed2 = seed1;
            seed1 = seed4;
        }
        long long ret = 0;
        long long lastans = 0;
        int y = 0;
        // 生成n组询问
        for(int i=1;i<=n;i++){
            // 获取每次询问的结果
            long long z = ans(x, y);
            // 将询问结果相加取模
            ret = (ret + z) % mod;
            lastans = z;
            x = (int) ((x+lastans)^ret)%n + 1;
            y = (int) lastans;
        }
        return ret;
    }

    // 生成询问结果
    long long ans(int x, int y){
        long long a = 0;
        int i = x;
        // 从x往根节点计算
        while(i != 1){
            a += (y + 2*i) ^ (y+i);
            i = (int)parent[i];
        } 
        a += (y + 2) ^ (y + 1);
        return a;
    }

时间复杂度：与Java实现相同；
空间复杂度：与Java实现相同。