in this problem (http://codeforces.me/contest/165/problem/D) there is a condition which makes it easy which is "there exists no more than one vertex, whose degree is more than two" so what if this condition didnot exist ?
in this problem (http://codeforces.me/contest/165/problem/D) there is a condition which makes it easy which is "there exists no more than one vertex, whose degree is more than two" so what if this condition didnot exist ?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
I think this is a more simple variation of HLD. The quote:
means that the graph can be easily separated in chains. Find the vertex with degree greater than 2(if such a vertex exists). Then this is the beginning of all chains. If such vertex doesn't exist, find an unused vertex with degree 1 and make it the beginning of a new chain. Repeat this until all vertexes become used. Then for each chain build some data structure that can handle this queries(for example you can use a fenwick tree).
I think u got me wrong I meant the problem above but with removing the condition so the graph mustn't be a group of chains
Hmm, yes, I didn't understand the question. But I think if the graph is just a tree(not a beard graph), HLD does the job.
Can u explain solution with HLD?
Do you know what HLD is? Have you learnt it? If no, just learn it. Split the graph in chains using HLD and for each chain build a fenwick tree/segment tree where the leaves in the tree are the edges in the chain. If you have to change the color of the i-th edge, just find its chain and update the tree. If you have to answer if the path between A and B consists of black edges only, then just find the paths between A and LCA(A,B) and between B and LCA(A,B). If they consist of black edges only, then the answer is YES. Otherwise, it's NO.
Another option is to read the editorial where is described a similar idea to the one that I described some minutes ago.
You may find this helpful: http://codeforces.me/blog/entry/10025