木の重心の計算

[zawa-tin]

名前

概要

参考

(履修に利用したサイト、なるべく細かく載せておく)

関連issue

verifyリンク

追加ファイル名

進行状況

• [ ] コードを書いた
• [ ] AtCoderかAOJでverify(書いたコードを利用してAC)した
• [ ] documentを書いた
• [ ] verifyコードの解説を書いた

[zawa-tin]

u32 centroid(const Tree& T, u32 v, const std::vector<bool>& removed, std::vector<u32>& sz) {
}

みたいな感じで重心を返す関数だけ作ろうかな。重心分解自体をライブラリ化するのは難しそう。

[zawa-tin]

class Centroid {
public:
   u32 centroid(u32 v);
   bool isRemoved(u32 v);
   void remove(u32 v);
   usize size(u32 v);
   std::vector<u32> subtree(u32 v);
private:
   Tree g;
   std::vector<usize> sz;
   std::vector<bool> removed;
};

こうかな。