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 (usually) multiple lychee fruits in each node).

Ada will give you many queries, for harvesting lychees, consisting of 3 numbers: index of node U, Ith ancestor, L new lychees, meaning, that she wants to harvest lychees of Ith ancestor of node U. Afterward L new lychee fruits will grow on the node.

She wants you to sum all those harvest-values 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 x0, a, b. The next term could be counted as xi=(a*xi-1+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 xi%100003 (105+3). Afterward there will be Q queries, giving you U, I, L (denoting XT as next xi), 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, xi, a, b: 1 ≤ N ≤ 2*105, 1 ≤ Q ≤ 4*107, 0 ≤ a, b, x0 < 1000000007

The next N-1 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
fahimcp495: 2020-09-16 20:57:05

got AC with O(N) preprocessing & O(logN) per query using Ladder Decomposition :)

But got TLE with O(NlogN) preprocessing & O(1) per query using Ladder Decomposition plus Jump Pointers :(

ishancosmos25: 2019-04-30 17:08:17

How to solve this problem?

morass: 2017-08-04 21:04:47

@hodobox: Well I expected the time-limit 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: 2017-08-04 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: 2017-08-04 14:05:04
morass: 2017-08-04 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: 2017-08-04 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: 2017-08-04 04:15:25
morass: 2017-08-04 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 :/

The memory usage for this problem can be greatly reduced, yet it was not expecting it to have such big impact on the problem :'(

morass: 2017-08-04 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: 2017-08-04 03:10:34
[Rampage] Blue.Mary: 2017-08-04 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...

To others who get stuck on this problem: try to search for parameters about the judge cluster used by SPOJ.

Last edit: 2017-08-04 01:51:28
hodobox: 2017-08-03 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: 2017-08-04 00:12:15

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