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.
/*Idea: since it's a DP problem, see if we can build the configurations of a node based on its children. Answer is yes.For any node, there are two cases which are helpful to build the solution for its parent:(1) the node's subtree is a good configuration, excluding its parent;(2) the node's subtree is a nearly good configuration, it's good when its parent is included, i.e. the direct children of the node all have the same color, which is the opposite of the node (itself is bad, rest is good); when the parent of this node has the same color, the node becomes good, therefore, this nearly good configuration becomes good.So we need to save above two numbers for each node.Denote G1r to be the number of good configurations for node 1 when it is red, i.e. (1);Denote B1r to be the number of nearly good configurations for node 1 when it is red, i.e. (2);Obviouse by symmetry: G1r = G1b, B1r = B1b.Let's look at an example, we have 3 nodes: 1, 2, 3, 1 is head and the parent of 2 and 3.B1r = G2b * G3b: 1 is red, 2 and 3 are blue, this is by definition from (2)What's G1r then? Since for node 2 and 3, each has 4 numbers, let's do first attempt by naive multiplication rule:Version 1: G1r = (G2b + G2r + B2r + B2b) * (G3b + G3r + B3r + B3b)We realize: given 1 is red, B2b should be removed, because 1 being red doesn't save 2 from being a bad node, so does B3b, which gives:Version 2: G1r = (G2b + G2r + B2r) * (G3b + G3r + B3r)We then realize: G2b and G3b can not happen at the same time, otherwise 1 is connected to two blue nodes, making 1 a bad nodeTherefore, we haveVersion 3: G1r = (G2b + G2r + B2r) * (G3b + G3r + B3r) - G2b * G3b, which is the correct one.In the c++ code: G stands for Gnr/Gnb, B stands for Bnr/Bnb;*/constlongMOD=long(1e9+7);structNode{inta{0};boolvisited{false};unordered_set<Node*>connected;Node(intm):a(m){}};classGraph{private:vector<Node>nodes;public:Graph(intn){for(inti=1;i<=n;i++){nodes.push_back(Node(i));}}voidadd_edge(intu,intv){nodes[u-1].connected.insert(&nodes[v-1]);nodes[v-1].connected.insert(&nodes[u-1]);}longcount();voidsolve(Node*n,vector<longlong>&G,vector<longlong>&B,vector<int>&P);// ATTN: long long instead of longvoidset_parents(Node*n,vector<int>&P);voidset_visited_all(boolb){for(auto&n:nodes)n.visited=b;}};voidGraph::set_parents(Node*node,vector<int>&P){node->visited=true;for(auton:node->connected){if(n->visited)continue;P[n->a]=node->a;if(n->connected.size()>1)set_parents(n,P);}}voidGraph::solve(Node*node,vector<longlong>&G,vector<longlong>&B,vector<int>&P){node->visited=true;if(P[node->a]&&node->connected.size()==1){// ATTN: leaf node, be careful when head has only one childB[node->a]=1;G[node->a]=0;return;}for(auton:node->connected){if(n->visited)continue;if(G[n->a]==-1)solve(n,G,B,P);}B[node->a]=1;G[node->a]=1;for(auton:node->connected){if(n->a==P[node->a])// skip parentcontinue;B[node->a]*=G[n->a]%MOD;// ATTN: do MOD as we goG[node->a]*=(2*G[n->a]+B[n->a])%MOD;B[node->a]%=MOD;G[node->a]%=MOD;}G[node->a]-=B[node->a];while(G[node->a]<0)// ATTN: be careful when G < BG[node->a]+=MOD;}longGraph::count(){size_tn=nodes.size();vector<longlong>G(n+1,-1),B(n+1,-1);vector<int>P(n+1,0);inta=rand()%n;a=0;set_parents(&nodes[a],P);set_visited_all(false);solve(&nodes[a],G,B,P);return2*G[a+1]%MOD;}
Cookie support is required to access HackerRank
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 →