• + 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;
    }