We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I believe the following code is much easier to understand than the editorial:-
enum{safe,unsafe};vector<vector<long>>M,dp;vector<bool>vis;#define h 1000000007voiddfs(intx){vis[x]=1;longsf=1,usf=1;for(autoy:M[x]){if(vis[y])continue;dfs(y);usf*=dp[y][safe],usf%=h;sf*=dp[y][safe]+dp[y][safe]+dp[y][unsafe],sf%=h;}sf-=usf,sf+=h,sf%=h;dp[x][safe]=sf;dp[x][unsafe]=usf;}// Complete the kingdomDivision function below.intkingdomDivision(intn,vector<vector<int>>roads){M.clear();M.resize(n);dp.clear();dp.resize(n,vector<long>(2));vis.clear();vis.resize(n);for(autox:roads){x[0]--,x[1]--;M[x[0]].push_back(x[1]);M[x[1]].push_back(x[0]);}dfs(0);for(auto&x:dp){for(auto&y:x)cerr<<y<<' ';cerr<<'\n';}return(2*dp[0][safe])%h;}
Kingdom Division
You are viewing a single comment's thread. Return to all comments →
I believe the following code is much easier to understand than the editorial:-