You are viewing a single comment's thread. Return to all 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; }
Seems like cookies are disabled on this browser, please enable them to open this website
Kingdom Division
You are viewing a single comment's thread. Return to all comments →