how to solve that problem
source link: https://codeforces.com/blog/entry/113992
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
How to solve such a problem: Given a set and a tree, it supports adding points to the set, deleting points, and querying whether the points within the set are connected blocks on the tree
|
56 minutes ago, # | are you talking about the "Union Find" data structure? UnionFind |
|
23 minutes ago, # | You can simply save the total number of connected blocks for maintenance. Because every point in the tree is a cut point, it is easy to calculate. After adding a point x, the number of connected blocks increases by "1 — the number of points that Adjacent to x on the tree and in the set". For deleting a point, just reduce the same value. Sample Then, this problem is similar to Facebook hacker cup 2022 Qualification Round Problem D. Classify the relationship between the number of point degrees and the size of . I'm not sure if I can do it faster, but I think it's hard. |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK