5412: Starch Cat

Chen is a cute cat. She loves Starch very much. Today She would like to steal some.

Chen lives in a village. The houses in the village connect as a tree. The house marked i stores a_i kg starch. She will only steal the houses on the shortest path from the house marked u to the house marked v . To avoid being caught, if Chen chooses to steal the house marked x, every house directly connected with the house marked x won't be stolen.

Now, you should answer Chen how much starch she can steal at most?

Because the amount of queries is too large, you need to use the random number generator as follows. We use lastans to represent the answer to the last query. You need to update lastans after each query.

The random number generator will cost no more than 500ms. 

struct Rand{

    unsigned int n,seed;

    Rand(unsigned int n,unsigned int seed)

    :n(n),seed(seed){}

    int get(long long lastans){

        seed ^= seed << 13;

        seed ^= seed >> 17;

        seed ^= seed << 5;

        return (seed^lastans)%n+1;

    }

};

For the j^thquery, you need to use the generator to get 3  integers  . And you should calculate the answer . After that, use  to update lastans. The following code is for reference. 

long long lastans=0,ans=0;

constexpr int P=998244353;

Rand rand(n,seed);

for(int i=0;i<m;i++){

    int u=rand.get(lastans);

    int v=rand.get(lastans);

    int x=rand.get(lastans);

    lastans=query(u,v);//calculate the answer

    ans=(ans+lastans%P*x)%P;

}

//print 'ans'

The first line contains 3 integers  is the number of houses. is the number of queries.

The second line contains n integers. The i^th integer is 

The third line contains n-1 integers. The i^th integer f_i represents to the house marked i+1 is connected to house marked f_i It is guaranteed that the houses connect as a tree.

Then, you need to use n and seed to initialize the generator.

For the j^th query, you need to use the generator to get 3 integers . And you should calculate the answer ans_j. After that, use ans_j to update lastans. You can refer to the second code in the description.

Only one integer,

5 3 1
2 1 1 2 2
1 1 2 2

14