ADALICI  Ada and Lychees
As you might already know, Ada the Ladybug is a farmer. She grows lychee tree. Unlike a cherry tree, lychee tree really forms a tree (obviously a rooted tree  in node 0). The lychee fruits grow in bunches (there are (usualy) multiple lychee fruits in each node).
Ada will give you many queries, for harvesting lychees, consisting of 3 numbers: index of node U, I^{th} ancestor, L new lychees, meaning, that she wants to harvest lychees of I^{th} ancestor of node U. Afterward L new lychee fruits will grow on the node.
She wants you to sum all those harvestvalues and output the sum. Value of harvest can be counted as X*W, where X is number of node where you'll harvest and W is the number of lychees in it.
Also note that input's format won't be easy (as usual). You will be given description of the tree and x_{0}, a, b. The next term could be counted as x_{i}=(a*x_{i1}+b)%MOD, where % means modulo and MOD is equal to 10^9+7 (1000000007)
Firstly, you can set the number of lychees on each node: The number of lychee fruits on node i is equal to x_{i}%100003 (10^{5}+3). Afterward there will be Q queries, giving you U, I, L (denoting XT as next x_{i}), U=XT%N, I=XT%(D[U]+1) (where D indicates DEPTH  root has depth 0), L=XT%100003 [priority of XT is from left to right].
NOTE: Parent of every node will always have lesser ID than the node itself (since the lychees far away from root are much more juicy).
Input
The first line contains five integers N, Q, x_{i}, a, b: 1 ≤ N ≤ 2*10^{5}, 1 ≤ Q ≤ 4*10^{7}, 0 ≤ a, b, x_{0} < 1000000007
The next N1 lines contains two integers 0 ≤ a < b < N, the branch connecting two nodes.
Output
Print a single line  the number sum of values over all queries.
Example Input
5 3 1 1 1 0 1 1 2 0 3 2 4
Example Output
13
Additional Information
#LYCHEES: 1 2 3 4 5 QUERY 1: 1 1 8 QUERY 2: 4 2 11 QUERY 3: 2 1 14
Example Input 2
5 5 2 3 4 0 1 1 2 2 3 2 4
Example Output 2
113299
Additional Information 2
#LYCHEES: 2 10 34 106 322 QUERY 1: 0 0 8746 QUERY 2: 2 1 36188 QUERY 3: 1 0 77101 QUERY 4: 4 2 81719 QUERY 5: 0 0 26368
Example Input 3
10 100 666 561 14159 0 1 0 2 1 3 1 4 2 5 2 6 3 7 3 8 4 9
Example Output 3
9060951
Example Input 4
20 10000 30355495 415740782 580959825 0 1 1 2 2 3 3 4 3 5 0 6 6 7 7 8 8 9 3 10 1 11 3 12 11 13 3 14 3 15 4 16 16 17 8 18 17 19
Example Output 4
1939449924
hide comments
morass:
20170804 21:04:47
@hodobox: Well I expected the timelimit to be slightly different so it could be distinguished "normally"  but somehow huge cache problems came ^_^ ... Yet seems the optimal solution shall not have "much" problem with cache anyway. Have nice day ^_^ 

hodobox:
20170804 12:49:51
@morass I was wondering if you were trying to not let logn pass with the huge amount of query, although strictly the 'number of operations' is still way within limits considering the huge TL, just that accessing an array becomes a huge constant (I suppose that somewhat counts as 'making sure logn won't pass' in a weird way). Anyway thanks for the pdf, I've just recently started doing problems with this theme so I'll think I'll save this for later :). glhf Last edit: 20170804 14:05:04 

morass:
20170804 11:44:23
@[Rampage] Blue.Mary: Hello, The first accepted solution doesn't fullfill it  it runs over 8 seconds, anyway the new solutions (with runtime under 20s) seems to have maximum runtime 2.5 seconds  so yes! 

[Rampage] Blue.Mary:
20170804 04:11:04
@Morass: What's the maximum running time (for one test case) of my last program? Does it fit into previous time limit (5.5sec)? Last edit: 20170804 04:15:25 

morass:
20170804 03:07:25
@[Rampage] Blue.Mary: Oh well sorry for it :'( To be honest I didn't expect the cache problems around this problem  I just wanted to distinguish the O(1)/log(N) complexity for query :/


morass:
20170804 03:01:47
@hodobox: Well seems your algorithm is O(log(N)) per query (is it right?)  I think it won't pass anyway :'( Or did I misunderstood your algorithm? :O [ http://www2.compute.dtu.dk/courses/02282/2015/levelancestor/levelancestor1x1.pdf ] this one might be helpful for it  hope this hinting won't matter since there are "such problems" :/ Last edit: 20170804 03:10:34 

[Rampage] Blue.Mary:
20170804 01:48:30
@Morass: Yesterday I spent a lot of time to fight with cache  I think the key to this problem is NOT time complexity (per query). To cache efficiently makes the program run faster than expected...


hodobox:
20170803 23:45:32
I seem to have a problem with caching as well. I made a test case N=2*10^5 Q=4*10^7 where the tree is just a long line, and it runs in 2.5s without the single line 'U = g[U][i];' but 35s with it (on my PC). I don't know how to optimize it any further, did you manage to do it @morass? Or do you have a different solution in which looking at several indices in that big an array is not necessary so it does not take up 90% of the time? Last edit: 20170804 00:12:15 

morass:
20170803 14:07:39
@[Rampage] Blue.Mary: I've modified (drastically) time limit. Your solution seems to be correct (good complexity) ~ so I admit it shall pass. Hope the timelimit won't allow more naive approaches. I'm not much sure why is your solution so slow even though the complexity is good [imho it might be problem with caching, since the arrays are BIG  but I might be wrong :/ ] ... anyway some modification shall make it pass [maybe resubmiting / other C languages / swapping "fat" dimensions] (I didn't wan't to increase it too much so it might be tight). Sorry for the inconvenience  and wishing you good day!

Added by:  Morass 
Date:  20170803 
Time limit:  9s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 