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.
constone=BigInt(1);constmod=BigInt(10**9+7);functionmodMul(a,b){return(a*b)%mod;}functionmodAdd(a,b){return(a+b)%mod;}functionmodSub(a,b){return(mod+a-b)%mod;}/** * two type of nodes x(Reggy) & y(Betty) * result for a node has 4 values * 1) xDiff - combinations when node is x and parent is y * 2) xSame - combinations when node is x and parent is x * 3) yDiff - combinations when node is y and parent is x * 4) ySame - combinations when node is y and parent is y */functioncalc(childResults){letxAlly=one;// node x and children all yletyAllx=one;// node y and children all xletxAll=one;// node x and any childrenletyAll=one;// node y and any childrenfor(const[xDiff,xSame,yDiff,ySame]ofchildResults){xAlly=modMul(xAlly,yDiff);yAllx=modMul(yAllx,xDiff);xAll=modMul(xAll,modAdd(xSame,xDiff));yAll=modMul(yAll,modAdd(yDiff,ySame));}return[modSub(xAll,xAlly),xAll,modSub(yAll,yAllx),yAll];}functionfind(tree){constresults=[];/** * using a stack array for traversal, * as recursion overflows for 1 usecase */conststack=[['0',1,-1,results]];while(stack.length>0){const[t,...rest]=stack.pop();switch(true){case(t==='0'):{const[node,parent,results]=rest;constcResults=[];stack.push(['1',results,cResults]);for(constcoftree[node]??[]){if(c===parent)continue;stack.push(['0',c,node,cResults]);}break;}case(t==='1'):{const[results,cResults]=rest;results.push(calc(cResults));break;}}}const[[xDiff,,yDiff]]=results;returnmodAdd(xDiff,yDiff);}functionkingdomDivision(n,roads){consttree={};for(const[u,v]ofroads){tree[u]=tree[u]??[];tree[v]=tree[v]??[];tree[u].push(v);tree[v].push(u);}returnfind(tree);}
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 →
js