Sort by

recency

|

64 Discussions

|

  • + 4 comments
    for the dfs function return pair, the return value means:
    1. pair.first: valid combination count if current node color different from parent, or current node has no parent (eg. lonely if all children colors are different)
    2. pair.second: valid combination count if current node color same as parent (eg. never be lonely no matter of what children colors)
    
    dfs(1, -1) means that we start from node 1 as root, and no parent
    for the root node 1, because it has no parent, so we use pair.first, and because it can be blue or red, so we times by 2
    
    pair<long,long> current=dfs(edges[index][i],index)
    we consider only valid children nodes, if the children nodes will cause war, then we'll not count them
    "lonely" means that all the children colors are different from current node, which means that all children are valid, but the current node causes war (eg. current node red and all children nodes blue, or otherwise)
    "total" means that all the children colors can be either same or different, because the current node already supported by the parent
    "total-lonely" means that the valid combination count if current node is different from parent (eg. not count if all children nodes different from the current one)
    "total" means all combination count, since the current node color is same as parent
    
    vector<long> edges[100001];
    long d=1000000007;
    pair<long,long> dfs(int index,int p)
    {
        long lonely=1,total=1;
        for(int i=0;i<edges[index].size();i++)
        {
            if(edges[index][i]==p) continue;
            pair<long,long> current=dfs(edges[index][i],index);
            lonely=(lonely*current.first)%d;
            total=(total*(current.first+current.second))%d;
        }
        return {(total-lonely+d)%d,total};
    }
    int kingdomDivision(int n, vector<vector<int>> roads) 
    {
        for(auto& road: roads)
            edges[road[0]].push_back(road[1]), edges[road[1]].push_back(road[0]);
        pair<long,long> result=dfs(1,-1);
        return (2*result.first)%d;
    }
    
  • + 0 comments

    the test case 1 gives me a simple data Input (stdin):

    7; 1 2; 1 5; 2 3; 2 4; 5 6; 7 5;

    How is that possible to divide it six ways? I count only 4 because it is a particular case of the case in example, is not it?

  • + 0 comments

    Recursive solution doesn't work on Python because of the maximum recursion limit (e.g. Test 11 has a tree with 72000 depth). sys.setrecursionlimit(100000) doesn't work because Python still crashes at ~2670 level of recursion. What works: using Kahn's algorithm to iteratively go from the leaves to the root. New style Prescription wooden glasses

  • + 0 comments

    took me AGES to debug

    O(n)

    long mod = 1000000007;
    
    class Node {
    public:
        int number;
        long divide;
        long loneRed;
        Node* parent;
        vector<Node*> children;
        Node (int num, long div, long free, Node* par) {
            number = num; divide = div; loneRed = free; parent = par;
        }
    };
    
    Node* treeMaker (int n, const vector<vector<int>>& roads) {
        Node* root = new Node(1, 0, 1, NULL);
        vector<vector<int>> adj(n+1);
        for (int i=0; i < roads.size(); i++) {
            adj[roads[i][0]].push_back(roads[i][1]);
            adj[roads[i][1]].push_back(roads[i][0]);
        }
        queue<Node*> Q;
        Q.push(root);
        while (!Q.empty()) {
            Node* t = Q.front();
            for (int i=0; i < adj[t->number].size(); i++) {
                if (t == root or adj[t->number][i] != t->parent->number) {
                    Node* child = new Node(adj[t->number][i], 0, 1, t);
                    t->children.push_back(child);
                    Q.push(child);
                }
            }
            Q.pop();
        }
        return root;
    }
    
    void dehaka (Node* current) {
        if (current->children.empty()) return;
        long a = 1, b = 1;
        for (Node* child : current->children) {
            dehaka(child);
            b = (b * child->divide) % mod;
            a = (a * (2 * child->divide + child->loneRed)) % mod;
        }
        current->loneRed = b;
        current->divide = (a - b + mod) % mod;
    }
    
    int main()
    {
        int n, k, l;
        vector<vector<int>> roads;
        cin >> n;
        for (int i=1; i <= n-1; i++) {
            cin >> k >> l;
            roads.push_back({k, l});
        }
        Node* root = treeMaker(n, roads);
        dehaka(root);
        cout << (2 * root->divide) % mod;
    }
    
  • + 1 comment

    Why this is medium difficulty?