backTrack(当前层数，棋盘):
    for: 当前层的每个位置
        放置一个棋子到这个位置
        backTrack(下一层, 棋盘) // 深入到下一层
        取消将棋子放到这个位置 // 回溯，以便于尝试当前层的下一个位置

class Solution {
public:
    vector<int> used;
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        vector<int> buckets(k, 0);
        used.resize(nums.size(), false);

        sort(nums.rbegin(), nums.rend());

        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum % k != 0) {
            return false;
        }

        int tar = sum / k;
        if(nums[0] > tar) {
            return 0;
        }

        vector<unordered_set<int>> memo(nums.size()); // for node[i], memo[i][j]means： node[i] put into a bucket with value j will failed
       
        return backTrack(nums, buckets, 0, tar, memo);
    }

    // for every number, try bucket from 0 to k-1
    bool backTrack(vector<int>& nums, vector<int>& buckets, int st, int tar, vector<unordered_set<int>>& memo) {
        
        // 所有数字都放进去了，成功了
        if(st == nums.size()) {
            return true;
        }
        
        for(int buc = 0; buc < buckets.size(); ++buc) {
            if(0 == memo[st].count(buckets[buc])) {
            // if(buckets[i]) {
                buckets[buc] += nums[st]; // put it into buc
                // used[st] = true;
                if(buckets[buc] == tar || (tar - buckets[buc] >= nums.back())) {
                    // cout << "to buc: " << buc << endl;
                    if(backTrack(nums, buckets, st + 1, tar, memo)) {
                        return true; // 提前返回，因为已经找到一个结果
                    }
                }
                buckets[buc] -= nums[st];
                
                // 如果nums[st] 放入 buckets[buc]失败了，那么后面值相同的桶都会失败，就不用放了
                memo[st].insert(buckets[buc]);
            }
        }

        // 说明放错桶的不是st，而是nums[0 : st-1]中的某个，于是把memo清除掉
        memo[st].clear();

        return false;
    }
}

class Solution {
public:
    vector<int> used;
    bool fin = false;
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        vector<int> buckets(k, 0);
        used.resize(nums.size(), false);

        sort(nums.rbegin(), nums.rend());

        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum % k != 0) {
            return false;
        }

        int tar = sum / k;
        if(nums[0] > tar) {
            return 0;
        }
       
        int useCnt = 0; 

        vector<unordered_set<int>> memo(nums.size());
        backTrack(nums, buckets, 0, tar, useCnt, memo);

        return fin;
    }

    // for every number, try bucket from 0 to k-1
    void backTrack(vector<int>& nums, vector<int>& buckets, int st, int tar, int& useCnt,  vector<unordered_set<int>>& memo) {
        if(fin) {
            return ;
        }

        if(useCnt == nums.size()) {
            bool tmp = true;
            for(auto& buc : buckets) {
                tmp = tmp && (buc == tar);
            }
            if(tmp) {
                fin = true;
                return;
            }
        }

        if(useCnt == nums.size()) {
            return; // return true就行
        }
        

        for(int buc = 0; buc < buckets.size(); ++buc) {
            if(0 == memo[st].count(buckets[buc])) {
                buckets[buc] += nums[st]; // put it into buc
                ++useCnt;
                if(buckets[buc] == tar || (tar - buckets[buc] >= nums.back())) {
                    // cout << "to buc: " << buc << endl;
                    backTrack(nums, buckets, st + 1, tar, useCnt, memo); 
                }

                buckets[buc] -= nums[st];
                
                // 如果nums[st] 放入 buckets[buc]失败了，那么后面值相同的桶都会失败，就不用放了
                memo[st].insert(buckets[buc]);
                
                --useCnt;    
            }
        }

        // 说明放错桶的不是st，而是nums[0 : st-1]中的某个，于是把memo清除掉
        memo[st].clear();
    }
}

class Solution {
public:
    int m,n;
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};
    int tarSum = 0;
    int edX, edY;

    int backTrack(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y, int curSum) {
        if(x == edX && y == edY) {
            // cout << "yes: " << curSum << endl;
            if(curSum == tarSum) {
                return 1;
            } else {
                return 0;
            }
        }

        int ways = 0;
        for(int mv = 0; mv < 4; ++mv) {
            int nextX = x + dx[mv];
            int nextY = y + dy[mv];
            if(0 <= nextX && nextX < m && 0 <= nextY && nextY < n && \
                !vis[nextX][nextY] && \
                -1 != grid[nextX][nextY]
            ) {
                vis[nextX][nextY] = true;
                ways += backTrack(grid, vis, nextX, nextY, curSum + 1);
                vis[nextX][nextY] = false;
            }
        }

        return ways;
    }
    

    int uniquePathsIII(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();

        // just backTracking all 
        vector<vector<bool>> vis(m, vector<bool>(n, false));
        
        int x, y;
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(1 == grid[i][j]) {
                    x = i; y = j;
                } else if(2 == grid[i][j]) {
                    edX = i; edY = j;
                    ++tarSum;
                } else  {
                    tarSum += (grid[i][j] == 0);
                }
            }
        }
        // cout << tarSum << endl;

        int curSum = 0;
        vis[x][y] = true;
        return backTrack(grid, vis, x, y, curSum);
    }
};

class Solution {
public:
    void swap(int& a, int& b) {
        int c = a;
        a = b;
        b = c;
    }

    bool judge(double tar) {
        double x = sqrt(tar);
        if(floor(x) == x) {
            return true;
        }
        return false;
    }

    void print(vector<int>& vec) {
        for(auto i : vec) {
            cout << i <<" ";
        }cout <<"\n";
    }

    unordered_set<string> rmDup;
    
    // memo thah: cal[st][num] in pos st, whethter num has been visited
    unordered_map<int, unordered_map<int, bool>> cal;

    // st means : we are choosing a num for nums[st]
    // and we should be sure that: nums[st] and nums[st-1] is able to sqrt 
    int permutationCheck(vector<int>& nums, int st) {
        if(st == nums.size()) {
            string tmp = "";
            for(auto& i : nums) {
                tmp += to_string(i);
            }
            if(rmDup.insert(tmp).second) {
                return 1;
            }
            return 0;
        }

        int res = 0;
        for(int i = st; i < nums.size(); ++i) {
            swap(nums[i], nums[st]);
            // cout << "level: " << st << " ";
            // print(nums);
            if(st == 0) {
                if(!cal[st][nums[st]]) {
                    res += permutationCheck(nums, st + 1);
                    cal[st][nums[st]] = true;
                }
            } else {
                if(judge(nums[st-1] + nums[st])) {
                    if(!cal[st][nums[st]]) {
                        res += permutationCheck(nums, st + 1);
                        cal[st][nums[st]] = true;
                    }
                }
            }
            swap(nums[i], nums[st]);
        }

        // when return, the permutated prefix: nums[:st-1] will change, so we clear the memo
        cal[st].clear(); 
        return res;
    }

    int numSquarefulPerms(vector<int>& nums) {
        int n = nums.size();
        if(1 == n) {
            return judge(nums.front());
        }

        // all sequence(permutation) and check each
        return permutationCheck(nums, 0);
    }
};

class Solution {
public:
    vector<vector<bool>> board; // top left is 0, 0
    int n, m; // n colums, m rows

    int finRes = INT_MAX;

    // start from left top
    pair<int, pair<int, int>> findPos(vector<vector<bool>>& board) {
        int x, y;
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(!board[i][j]) {
                    x = i; y = j;
                    // find len:
                    int u = x;
                    while(u < m && !board[u][y]) {
                        ++u;
                    }
                    int len = u - x;

                    int v = y;
                    while(v < n && !board[x][v]) {
                        ++v;
                    }
                    len = min(len, v - y);

                    return {len, {x, y}};
                }
            }
        }

        return {-1, {-1, -1}};
    } 

    void fillSquareWith(vector<vector<bool>>& board, int x, int y, int len, bool content) {
        for(int i = x; i < x + len; ++i) {
            for(int j = y; j < y + len; ++j) {
                board[i][j] = content;
            }
        }
    }

    void backTrack(vector<vector<bool>>& board, int& leftCnt, int curRes) {
        if(finRes <= curRes) {
            return ;
        }
        if(0 == leftCnt) {
            finRes = min(finRes, curRes);
            return ;
        }
        
        // find first zero pos along the boarder, or the next 1
        auto p = findPos(board);
        int len = p.first;
        int x = p.second.first, y = p.second.second;
        // cout << "found max len: " << len << " x/y " << x << " " << y << endl;

        for(int l = len; l > 0; --l) {
            fillSquareWith(board, x, y, l, true);
            leftCnt -= l*l;
            
            // cout <<"ready to fill: x/y/l: " << x << "/" <<  y << "/" <<  l << "/" << "left: " << leftCnt << endl;
            // print(board);
            backTrack(board, leftCnt, curRes + 1);

            leftCnt += l*l;
            fillSquareWith(board, x, y, l, false);
        }
        
    }

    int tilingRectangle(int n, int m) {
        this->n = m;
        this->m = n;
        // cout << "this: " << this->n << " " << this->m << endl;
        board.resize(n, vector<bool>(m, 0));
        int leftCnt = n*m;
        int curRes = 0;
        backTrack(board, leftCnt, curRes);
        return finRes;
    }

    void print(vector<vector<bool>>& board) {
        for(auto v : board) {
            for(auto i : v) {
                cout << i << " ";
            }cout << "\n";
        }cout << "\n ---------- ";

    }
}

class Solution {
public:
    vector<int> wordScore;

    void printPool(unordered_map<char, int>& leftCharPool) {
        for(auto& [c, cnt] : leftCharPool) {
            cout << c << " " << cnt << endl;
        }
        cout << "---\n";
    }
    
    bool addOrRemove(string& word, unordered_map<char, int>& leftCharPool, bool add) {
        // cout << "add/rm: " << word << endl;
        if(add) {
            for(auto& c : word) {
                ++leftCharPool[c];
            }
        } else {
            unordered_map<char, int> curWord;
            for(auto& c : word) {
                ++curWord[c];
            }

            for(auto& [c, cnt] : curWord) {
                if(leftCharPool[c] < cnt) {
                    return false;
                }
            }

            printPool(leftCharPool);
            // remove the word from the pool
            for(auto& [c, cnt] : curWord) {
                // cout << "rm " << c << " : " << cnt << endl;
                leftCharPool[c] -= cnt;
            }
            // printPool(leftCharPool);

        }
        return true;
    }

    int backTrack(vector<string>& words, int st, unordered_map<char, int>& leftCharPool) {
        if(words.size() == st) {
            return 0;
        }

        int curScore = INT_MIN;
        // use it
        if(addOrRemove(words[st], leftCharPool, false)) {
            // cout << "using " << words[st] << endl;
            // printPool(leftCharPool);
            curScore = max(wordScore[st] + backTrack(words, st + 1, leftCharPool), curScore);
            // add it back
            addOrRemove(words[st], leftCharPool, true);
        }
        // not use it
        // cout << "not using" << words[st] << endl;
            // printPool(leftCharPool);
        curScore = max(backTrack(words, st + 1, leftCharPool), curScore);
        return curScore; 
    }
   
    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        // check all subsets of words using status compression
        // you may use status compression, but here we use backTrack
        unordered_map<char, int> leftCharPool;
        wordScore.resize(words.size(), 0);
        int wIdx = 0;
        for(auto& w : words) {
            for(auto& c : w) {
                wordScore[wIdx] += score[c - 'a'];
            }
            ++wIdx;
        }

        for(auto& c : letters) {
            ++leftCharPool[c];
        }
        
        int st = 0;
        return backTrack(words, 0, leftCharPool);
    }
};

class Solution {
public:
    class Trie {
    public:
        vector<Trie*> curLevel;
        bool isEnd = false;
        Trie() : curLevel(26, nullptr) {
        }

        void buildTrie(vector<string>& words) {
            for(auto& w : words) {
                auto curNode = this;
                for(auto& c : w) {
                    if(nullptr == curNode->curLevel[c - 'a']) {
                        curNode->curLevel[c - 'a'] = new Trie();
                    }
                    curNode = curNode->curLevel[c - 'a'];
                }
                curNode->isEnd = true;
            }
        }

        bool preInTrie(string& w) {
            auto curNode = this;
            for(auto& c : w) {
                auto nextLevel = curNode->curLevel[c - 'a'];
                if(nullptr == nextLevel) {
                    return false;
                }
                curNode = nextLevel;
            }
            return true;
        }

        bool wordInTrie(string& w) {
            auto curNode = this;
            for(auto& c : w) {
                auto nextLevel = curNode->curLevel[c - 'a'];
                if(nullptr == nextLevel) {
                    return false;
                }
                curNode = nextLevel;
            }
            return curNode->isEnd;
        }

    };

    void ableToMakeRes(vector<string>& hori, vector<string>& vert) {
        // cout << "> hori.size() " << hori.size() << endl;
        if(0 == vert[0].size()) {
            // cout << "> vert empty: " << endl;
            return;
        }

        for(auto& v : vert) {
            if(!root->wordInTrie(v)) {
                // cout << "> word failed: " << v;
                return ;
            }
        }
        
        int curSquare = vert[0].size() * vert.size();
        // cout << "> curSquare: " << vert[0].size() * vert.size() << endl;
        // cout << "> finSquare: " << finSquare << endl;
        if(curSquare > finSquare) {
            // cout << "updated!\n";
            finSquare = curSquare;
            resVec = hori;
        }
    }

    // try all possible permutation of rect with width = w
    void backTrack(
        vector<string>& curWords,
        vector<string>& hori,
        vector<string>& vert,
        vector<string>& resVec
    ) {
        int width = curWords[0].size();
        // cur found square bigger then all possilbe res from curWords
        if(finSquare > width * maxWordLen) return;

        // check if we obtain a res
        ableToMakeRes(hori, vert);

        for(auto& word : curWords) {
            hori.push_back(word);
            int vertCnt = 0;
            bool failed = false;
            for(int i = 0; i < width; ++i) {
                vert[i].push_back(word[i]);
                ++vertCnt;
                if(!root->preInTrie(vert[i])) {
                    failed = true;
                    break;
                }
            }
            // cout << "trying: " << word << " | with hori = " << hori.size() << endl;
            
            if(!failed) {
                // cout << "choosing: " << word << endl;
                // next level
                backTrack(curWords, hori, vert, resVec);
            }

            // backTrack
            // cout << "failed on: " << word << endl;
            hori.pop_back();
            for(int i = 0; i < vertCnt; ++i) {
                vert[i].pop_back();
            }
        }

    }
    unique_ptr<Trie> root;
    int finSquare = INT_MIN;
    vector<string> resVec;

    int maxWordLen = -1;

    vector<string> maxRectangle(vector<string>& words) {
        root = make_unique<Trie>();
        root->buildTrie(words);

        map<int, vector<string>, std::greater<int>> lenWords;
        for(auto& w : words) {
            lenWords[w.size()].push_back(w);
            maxWordLen = max(maxWordLen, static_cast<int>(w.size()));
        }

        for(auto& [w, curWords] : lenWords) {
            vector<string> hori;
            vector<string> vert(w, "");
            // cout << "w is: " << w <<endl;
            backTrack(curWords, hori, vert, resVec);
        }
        return resVec;
    }
};

#ifndef BOUNDARYVOLUMEHIERARCHY_H
#define BOUNDARYVOLUMEHIERARCHY_H

#include <algorithm>
#include <set>

#include "partitioner.h"

template <size_t DIMENSION>
class BoundaryVolumeHierarchy : public Partitioner<DIMENSION>
{
public:
    typedef typename Point<DIMENSION>::Vector Vector;
    static const size_t NUM_CHILDREN = 1 << DIMENSION;

    BoundaryVolumeHierarchy(const PointCloud<DIMENSION> *pointCloud)
        : Partitioner<DIMENSION>(pointCloud)
        , mRoot(this)
        , mParent(this)
        , mLeaf(true)
        , mLevel(0)
    {
        Rect<DIMENSION> extension = pointCloud->extension();
        mCenter = extension.center();
        mSize = extension.maxSize() / 2; // 点云最长边长的一半
        mIndices = std::vector<size_t>(pointCloud->size());
        std::iota(mIndices.begin(), mIndices.end(), 0);
        mLeafTable = std::vector<BoundaryVolumeHierarchy<DIMENSION>*>(pointCloud->size(), this);
    }

    BoundaryVolumeHierarchy(const BoundaryVolumeHierarchy &bvh) = delete;

    ~BoundaryVolumeHierarchy()
    {
        if (!isLeaf())
        {
            for (size_t i = 0; i < NUM_CHILDREN; i++)
            {
                if (mChildren[i] != NULL)
                {
                    delete mChildren[i];
                }
            }
        }
    }

    // 建立octree，直到每个叶子节点最多包含minNumPoints
    void partition(size_t levels = 1, size_t minNumPoints = 1, float minSize = 0.0f) override
    {
        if (!isLeaf())
        {
            for (size_t i = 0; i < NUM_CHILDREN; i++)
            {
                if (mChildren[i] != NULL)
                    mChildren[i]->partition(levels - 1, minNumPoints, minSize);
            }
        }
        else
        {
            // 递归层次用完了 || 叶子内部点数达到最小要求 || 最多只有一个点了 || 节点的边长小于最小限度
            if (levels <= 0 || mIndices.size() <= minNumPoints || mIndices.size() <= 1 || mSize < minSize) return;
            // create new centers
            Vector newCenters[NUM_CHILDREN];
            calculateNewCenters(newCenters);

            mLeaf = false;

            // create children
            float newSize = mSize / 2;
            for (size_t i = 0; i < NUM_CHILDREN; i++)
            {
                mChildren[i] = NULL;
            }

            // split points
            for (const size_t &index : mIndices)
            {
                // calculate child index comparing position to child center
                // 对于每个点，计算它位于当前节点的哪个子节点？
                size_t childIndex = calculateChildIndex(this->pointCloud()->at(index).position());
                if (mChildren[childIndex] == NULL)
                {
                    mChildren[childIndex] = new BoundaryVolumeHierarchy<DIMENSION>(this, newCenters[childIndex], newSize);
                    mChildren[childIndex]->mIndices.reserve(mIndices.size());
                }
                // 将这个点压入对应的子节点中
                mChildren[childIndex]->mIndices.push_back(index);
                // update current leaf where point is stored
                mRoot->mLeafTable[index] = mChildren[childIndex];
            }

            mIndices.clear();

            // partition recursively, 将可用层数减少1，将每一个子节点进入下一次细分
            for (size_t i = 0; i < NUM_CHILDREN; i++)
            {
                if (mChildren[i] != NULL) {
                    mChildren[i]->partition(levels - 1, minNumPoints, minSize);
                }
            }
        }
    }

    const Partitioner<DIMENSION>* getContainingLeaf(size_t index) const override
    {
        return mRoot->mLeafTable[index];
    }

    BoundaryVolumeHierarchy<DIMENSION>* child(size_t index)
    {
        return mChildren[index];
    }

    std::vector<const Partitioner<DIMENSION>*> children() const override
    {
        if (isLeaf()) return std::vector<const Partitioner<DIMENSION>*>();
        std::vector<const Partitioner<DIMENSION>*> children;
        for (size_t i = 0; i < NUM_CHILDREN; i++)
        {
            if (mChildren[i] != NULL)
                children.push_back(mChildren[i]);
        }
        return children;
    }

    const Partitioner<DIMENSION>* parent() const override
    {
        return mParent;
    }

    const Vector& center() const
    {
        return mCenter;
    }

    float cellSize() const
    {
        return mSize;
    }

    bool isRoot() const override
    {
        return this == mRoot;
    }

    bool isLeaf() const override
    {
        return mLeaf;
    }

    size_t octreeLevel() const
    {
        return mLevel;
    }

    size_t numPoints() const override
    {
        if (isLeaf())
        {
            return mIndices.size();
        }
        else
        {
            size_t numPoints = 0;
            for (size_t i = 0; i < NUM_CHILDREN; i++)
            {
                if (mChildren[i] != NULL)
                    numPoints += mChildren[i]->numPoints();
            }
            return numPoints;
        }
    }

    Rect<DIMENSION> extension() const override
    {
        return Rect<DIMENSION>(mCenter - Vector::Constant(mSize),
                            mCenter + Vector::Constant(mSize));
    }

    std::vector<size_t> points() const override
    {
        if (isLeaf())
        {
            return mIndices;
        }
        else
        {
            std::vector<size_t> points;
            for (size_t i = 0; i < NUM_CHILDREN; i++)
            {
                if (mChildren[i] != NULL)
                {
                    std::vector<size_t> childPoints = mChildren[i]->points();
                    points.insert(points.end(), childPoints.begin(), childPoints.end());
                }
            }
            return points;
        }
    }

    void getNeighborCells(std::vector<BoundaryVolumeHierarchy<DIMENSION>*> &neighbors)
    {
        BoundaryVolumeHierarchy<DIMENSION>* neighbor;
        for (size_t i = 0; i < DIMENSION; i++)
        {
            neighbor = getNeighborCellsGreaterOrEqual(i, false);
            getNeighborCellsSmaller(i, false, neighbor, neighbors);
            neighbor = getNeighborCellsGreaterOrEqual(i, true);
            getNeighborCellsSmaller(i, true, neighbor, neighbors);
        }
    }

private:
    BoundaryVolumeHierarchy *mRoot;
    BoundaryVolumeHierarchy *mParent;
    BoundaryVolumeHierarchy *mChildren[NUM_CHILDREN];
    Vector mCenter;
    float mSize;
    bool mLeaf;
    size_t mLevel;
    std::vector<size_t> mIndices;
    std::vector<BoundaryVolumeHierarchy<DIMENSION>*> mLeafTable;

    BoundaryVolumeHierarchy(BoundaryVolumeHierarchy *parent, const Vector &center, float size)
        : Partitioner<DIMENSION>(parent->pointCloud())
        , mRoot(parent->mRoot)
        , mParent(parent)
        , mCenter(center)
        , mSize(size)
        , mLeaf(true)
        , mLevel(parent->mLevel + 1)
    {
        for (size_t i = 0; i < NUM_CHILDREN; i++)
        {
            mChildren[i] = NULL;
        }
    }

    void calculateNewCenters(Vector centers[NUM_CHILDREN])
    {
        float newSize = mSize / 2;
        for (size_t dim = 0; dim < DIMENSION; dim++)
        {
            for (size_t i = 0; i < NUM_CHILDREN; i++)
            {
                int signal = (((i & (1 << (DIMENSION - dim - 1))) >> (DIMENSION - dim - 1)) << 1) - 1;
                centers[i](dim) = mCenter(dim) + newSize * signal;
            }
        }
    }

    size_t calculateChildIndex(const Vector &position)
    {
        size_t childIndex = 0;
        for (size_t dim = 0; dim < DIMENSION; dim++)
        {
            childIndex |= (position(dim) > mCenter(dim)) << (DIMENSION - dim - 1);
        }
        return childIndex;
    }

    size_t getIndexOnParent()
    {
        for (size_t i = 0; i < NUM_CHILDREN; i++)
        {
            if (mParent->mChildren[i] == this)
            {
                return i;
            }
        }
        throw "Could not find node on parent";
    }

    size_t getIncrement(size_t direction, bool greaterThan)
    {
        int increment = 1 << (DIMENSION - direction - 1);
        if (!greaterThan)
        {
            increment = NUM_CHILDREN - increment;
        }
        return increment;
    }

    BoundaryVolumeHierarchy<DIMENSION>* getNeighborCellsGreaterOrEqual(size_t direction, bool greaterThan)
    {
        if (isRoot())
        {
            return NULL;
        }
        else if (greaterThan && mParent->mCenter(direction) > mCenter(direction) ||
            !greaterThan && mParent->mCenter(direction) < mCenter(direction))
        {
            size_t index = getIndexOnParent();
            size_t increment = getIncrement(direction, greaterThan);
            return mParent->mChildren[(index + increment) % NUM_CHILDREN];
        }
        BoundaryVolumeHierarchy<DIMENSION>* node = mParent->getNeighborCellsGreaterOrEqual(direction, greaterThan);
        if (node == NULL || node->isLeaf())
        {
            return node;
        }
        size_t index = getIndexOnParent();
        size_t increment = getIncrement(direction, !greaterThan);
        return node->mChildren[(index + increment) % NUM_CHILDREN];
    }

    void getNeighborCellsSmaller(size_t direction, bool greaterThan, BoundaryVolumeHierarchy<DIMENSION>* neighbor,
                                 std::vector<BoundaryVolumeHierarchy<DIMENSION>*> &neighbors)
    {
        std::queue<BoundaryVolumeHierarchy<DIMENSION>*> candidates;
        if (neighbor != NULL) candidates.push(neighbor);
        while (candidates.size() > 0)
        {
            BoundaryVolumeHierarchy<DIMENSION>* front = candidates.front();
            candidates.pop();
            if (front->isLeaf())
            {
                neighbors.push_back(front);
            }
            else
            {
                for (size_t i = 0; i < NUM_CHILDREN; i++)
                {
                    if (front->mChildren[i] == NULL) continue;
                    if ((greaterThan && front->mCenter(direction) > front->mChildren[i]->mCenter(direction)) ||
                        (!greaterThan && front->mCenter(direction) < front->mChildren[i]->mCenter(direction)))
                    {
                        candidates.push(front->mChildren[i]);
                    }
                }
            }
        }
    }

};

template class BoundaryVolumeHierarchy<2>;
template class BoundaryVolumeHierarchy<3>;

typedef BoundaryVolumeHierarchy<2> Quadtree;
typedef BoundaryVolumeHierarchy<3> Octree;

#endif // BOUNDARYVOLUMEHIERARCHY_H

class Solution {
public:
    
    void Tarjan(vector<vector<int>>& g, int st, vector<int>& parent, vector<int>& low, vector<int>& dfsNo, int no, set<int>& cutPoints, vector<vector<int>>& cutEdges) {
        int rootChildNum = 0;
        low[st] = dfsNo[st] = no;
        for(auto neighbor : g[st]) {
            // if(parent[neighbor] == st) {
            //     continue;
            // }
            if(-1 != dfsNo[neighbor]) { // st -> neighbor 是一条回边
                if(parent[st] != neighbor) { // 且不在搜索子树内
                    low[st] = min(low[st], dfsNo[neighbor]); // 更新low[st]为所有能通过回边到达的最小的dfsNo
                }
            } else {
                parent[neighbor] = st;
                ++rootChildNum;
                
                ++no;
                // cout << "u/v " << st<<"/"<<neighbor << " " << no << endl;
                Tarjan(g, neighbor, parent, low, dfsNo, no, cutPoints, cutEdges);
                low[st] = min(low[st], low[neighbor]); // 更新为所有搜索子树节点中能够通过回边到达的最小的dfsNo
                
                if(-1 != parent[st] && dfsNo[st] <= low[neighbor]) {
                    cutPoints.insert(st);
                }
                if(dfsNo[st] < low[neighbor]) {
                    cutEdges.emplace_back(vector<int>{st, neighbor});
                }
            }
        }
        if(parent[st] == -1 && rootChildNum >= 2) {
            cutPoints.insert(st);
        }
    }

    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        // build graph
        vector<vector<int>> g(n);
        for(auto e : connections) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }

        vector<int> dfsNo(n, -1);
        vector<int> low(n, -1); // low[i]：i号节点以及其子树中所有的搜索节点仅通过 回边 能够到达的节点的dfs序号(回边：非搜索树上的边)
        vector<int> parent(n, -1); // 记录搜索树
        int no = 0;

        set<int> cutPoints;
        vector<vector<int>> cutEdges;
        dfsNo[0] = 0;
        Tarjan(g, 0, parent, low, dfsNo, no, cutPoints, cutEdges);
        for(auto i : cutPoints) {
            cout << i << " ";
        }
        cout << "low: ";
        for(auto i : low) {
            cout << i << " ";
        }
        cout << "\ndfsNo: ";
        for(auto no : dfsNo) {
            cout << no << " ";
        }
        return cutEdges;
    }
};

class Solution {
public:
    int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {
        unordered_map<int, unordered_map<int, int>> g;
        
        auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.first > b.first;
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);

        for(auto& e : edges) {
            int u = e[0];
            int v = e[1];
            int w = e[2];
            g[u][v] = w+1;
            g[v][u] = w+1;
        }

        // init dis
        vector<int> disRes(n, INT_MAX);
        map<int, bool> visited;
        visited[0] = true;
        disRes[0] = 0;
        pq.push({0, 0});
        // disRes[0] = 0;
        // for(auto& neighbor : g[0]) {
        //     int to = neighbor.first;
        //     int w = neighbor.second
        //     disRes[to] = w;
        //     pq.push({w, to});
        // }

        // contain 0 itSelf!
        int res = 0; 


        // dijstra
        while(pq.size() > 0) {
            auto node = pq.top();
            pq.pop();
            int u = node.second;
            int dis = node.first;

            // for disRes[u], every relax will push a new pair, so we need
            // to pass all old relaxed value
            if(disRes[u] < dis) {
                continue;
            }
            visited[u] = true;
            disRes[u] = dis;
            
            res += (disRes[u] <= maxMoves);

            // relax nodes by u
            for(auto& neighbor : g[u]) {
                int v = neighbor.first;
                int w = neighbor.second;
                // v has been proceed!
                if(!visited[v] && disRes[v] > disRes[u] + g[u][v]) {
                    disRes[v] = disRes[u] + g[u][v];
                    pq.push({disRes[v], v});
                    print(disRes);
                }
            }
        }

        // count sub nodes
        for(auto& e : edges) {
            int u = e[0];
            int v = e[1];
            int w = e[2];
            int curSubNodes = 0;
            if(visited[u]) {
                curSubNodes += max(maxMoves - disRes[u], 0);
            }
            if(visited[v]) {
                curSubNodes += max(maxMoves - disRes[v], 0);
            }
            curSubNodes = min(curSubNodes, w);
            // cout << "curSub/edge: " << curSubNodes << " " << "e: " << u << "->" << v << endl;
            res += curSubNodes;
        }


        return res;
    }
    void print(vector<int>& dis) {
        for(int i = 0; i < dis.size(); ++i) {
            cout <<dis[i] << " ";
        }cout << "\n";
    }
};

class Solution {
public:
    int dx[4] = {1,-1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int m, n;

    int bfs(vector<vector<pair<int, int>>>& g) {
        // start from 0, search first 0 wighted edges
        deque<pair<int, int>> curLevel; // <node, dis from 0,0>
        curLevel.push_front({0, 0});
        vector<bool> vis(m*n); 
        vector<int> disV(m*n, INT_MAX); 
        disV[0] = 0;
        int tar =  m * n - 1;
        
        
        int res = INT_MAX;
        while(0 != curLevel.size()) {
            // cout << "---" << endl;
            int curLevelSize = curLevel.size();
            while(curLevelSize-- > 0) {
                auto curNode = curLevel.front();
                curLevel.pop_front();
                // cout << curNode.first << "-> dis: " << curNode.second << endl;

                int curDis = disV[curNode.first];
                for(auto& [neighbor, dis] : g[curNode.first]) {
                    // cout << "from/to: " << curNode.first << "/ " << neighbor << endl;
                    int newDis = curDis + dis;
                    if(newDis < disV[neighbor]) {
                        curLevel.push_back({neighbor, dis});
                        // if(dis == 0) {
                        //     curLevel.push_front({neighbor, 0});
                        // } else {
                        //     curLevel.push_back({neighbor, 1});
                        // }
                        disV[neighbor] = newDis;
                    }
                    if(neighbor == tar) { 
                        res = min(res, disV[tar]); 
                    }
                }
            }
        }

        return res == INT_MAX ? 0 : res;
    }

    int minCost(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        vector<vector<pair<int, int>>> g(m * n);

        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                int curNode = j + i * n;
                // cout << "i/j" << i << " " << j << endl;
                for(int mvIdx = 0; mvIdx < 4; ++mvIdx) {
                    int nextI = i + dy[mvIdx];
                    int nextJ = j + dx[mvIdx];
                    if(0 <= nextI && nextI < m && 0 <= nextJ && nextJ < n) {
                        int nextNode = nextI * n + nextJ;
                        // cout << mvIdx << endl;
                        if(grid[i][j] == mvIdx + 1) {
                            g[curNode].push_back({nextNode, 0});
                            // cout << "to " << nextNode << " = " << 0 << " ";
                        } else {
                            g[curNode].push_back({nextNode, 1});
                            // cout << "to " << nextNode << " = " << 1 << " ";
                        }
                        // cout << "\n";
                    }
                }
                sort(g[curNode].begin(), g[curNode].end(), 
                    [](const pair<int, int>& a, const pair<int, int>& b) {
                        return a.second < b.second;
                });
            }
        }

        // bfs to get dis
        return bfs(g);
    }
}

class Solution {
public:
    
    class UF {
    public: 
        int rootNums;
        vector<int> parent;

        UF(int size) : rootNums(size - 1) {
            for(int i = 0; i < size; ++i) {
                parent.push_back(i);
            }
        }
        
        int find(int x) {
            int oldX = x;
            while(x != parent[x]) {
                // parent[x] = parent[parent[x]]; // compression path
                x = parent[x];
            }
            parent[oldX] = x; // the same as upwards
            return x;
        }

        bool merge(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if(rootX != rootY) {
                parent[rootX] = rootY;
                --rootNums;
                return true;
            }
            return false;
        }
    };
    
    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
        vector<vector<int>> aEdges;
        vector<vector<int>> bEdges;
        vector<vector<int>> abEdges;

        for(auto& e : edges) {
            if(1 == e[0]) {
                aEdges.push_back(e);
            } else if(2 == e[0]) {
                bEdges.push_back(e);
            } else  {
                abEdges.push_back(e);
            }
        }

        int removeEdgeCnt = 0;
        
        UF uf(n + 1);
        int abCnt = 0;
        // firstly add the common edges
        for(auto& e : abEdges) {
            if(!uf.merge(e[1], e[2])) {
                // cout << "ab: rm: " << e[1] << "-" << e[2] << endl;  
                ++removeEdgeCnt;
            } else {
                // cout << "ab: merge: " << e[1] << "-" << e[2] << endl;  
                ++abCnt;
            }
        }

        if(1 == uf.rootNums) {
            return edges.size() - abCnt;
        }
//  cout << "cur rmAB cnt: " << removeEdgeCnt << endl;
        UF ufA = uf;
        UF ufB = uf;
        // try to make alice all ok
        int aCnt = 0;
        for(auto& e : aEdges) {
            if(!ufA.merge(e[1], e[2])) {
                ++removeEdgeCnt;
                // cout << "a: rm: " << e[1] << "-" << e[2] << endl;  
            } 
        }
        // cout << "cur rmA cnt: " << removeEdgeCnt << endl;

        // try to make bob all ok
        int bCnt = 0;
        for(auto& e : bEdges) {
            if(!ufB.merge(e[1], e[2])) {
                ++removeEdgeCnt;
                // cout << "b: rm: " << e[1] << "-" << e[2] << endl;  
            }
        }

        //  cout << "cur rmB cnt: " << removeEdgeCnt << endl;
        if(1 == ufB.rootNums && 1 == ufA.rootNums) {
            return removeEdgeCnt;
        }
        return -1;
    }
};