# | User | Rating |
---|---|---|

1 | Benq | 3539 |

2 | tourist | 3532 |

3 | wxhtxdy | 3425 |

4 | Radewoosh | 3316 |

5 | ecnerwala | 3297 |

6 | mnbvmar | 3280 |

7 | LHiC | 3276 |

8 | Um_nik | 3260 |

9 | yutaka1999 | 3190 |

10 | TLE | 3145 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 192 |

2 | Radewoosh | 179 |

3 | tourist | 173 |

4 | Vovuh | 167 |

4 | antontrygubO_o | 167 |

4 | PikMike | 167 |

7 | rng_58 | 160 |

8 | majk | 157 |

9 | Um_nik | 154 |

10 | 300iq | 153 |

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/16/2019 04:58:32 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

First, notice that the graph of dependencies between variables is a forest. We call

ba "left child" ofaifais theXiofb. Similarly,bis a "right child" ifais theYiofb.Now consider variable

a, valuei, and the subtree rooted ina. We wantcounter[a][i]contain the number of all possible value assignments of the variables in the subtree such thata=iand that each of them respects the constraints (given byXiandYi).We notice that this value can be computed easily based on the values of the children of

a. It's the product ofsum(c,i)for each childcofa, wheresum(c,i)is the sum ofcounter[c][1..i]ifcis a right child or the sum ofcounter[c][i..100000]ifcis a left child.So, through recursion (well, actually dynamic programming), we can compute

counter[a][i]for allaand for alli. To get the final result we multiply, for all rootsrof the trees, the sum ofcounter[r][i]for all values ofi.Don't worry, it sounds more complicated than it actually is!

The complexity should be O(N) (with a factor of 100000 :) and it actually runs really fast: my implementation has an execution time of max. 0.04s.

counter[a][i]is zero wheni<Xaori>Ya.counter[a][i]you iterate overallchildren ofa(regardless of their type) and for each of them you compute the value ofsum(c,i)(wherecis the child you're currently iterating on). As I said, sum(c,i) is:counter[c][1] + ... + counter[c][i]ifcis a right child ofacounter[c][i] + ... + counter[c][100000]ifcis a left child ofa(this hardcoded constant is the maximum value ofXiandYi)When you have the values of

sum(c,i)for all children, you multiply themallto get the value ofcounter[a][i].I hope it's more clear now!

Thanks a lot ..

I'll have a try ..

-----------

How about this input:

3

2 3

1 a

b a

You can't get a fix count[r][i] for some node ..