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