So the problem goes like, we have colors designated to vertices of tree and we need to find distinct values in subtree of a vertex (queries).

Can anyone share/remember such a problem?

Thanks.

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

1 | Benq | 3650 |

2 | Radewoosh | 3648 |

3 | tourist | 3579 |

4 | ecnerwala | 3551 |

5 | Um_nik | 3494 |

6 | Petr | 3452 |

7 | ksun48 | 3432 |

8 | jiangly | 3349 |

9 | maroonrk | 3338 |

10 | Miracle03 | 3314 |

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

1 | 1-gon | 211 |

2 | awoo | 188 |

3 | Errichto | 186 |

3 | rng_58 | 186 |

5 | SecondThread | 183 |

6 | Um_nik | 176 |

6 | Ashishgup | 176 |

8 | maroonrk | 173 |

9 | antontrygubO_o | 171 |

10 | -is-this-fft- | 169 |

So the problem goes like, we have colors designated to vertices of tree and we need to find distinct values in subtree of a vertex (queries).

Can anyone share/remember such a problem?

Thanks.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/09/2021 17:09:21 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

http://codeforces.com/problemset/problem/375/D http://codeforces.com/problemset/problem/600/E

At first linearize the tree by Euler Tour. Then you can represent each subtree by a contiguous sub-array. Now the task is just counting number of distinct integers in a range of array. You can do that by normal MO's algo. Or you can use persistent segment trees to get per query solution.

There are other solution too, like you can do DSU on tree and solve the problem offline in .