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.
#include<algorithm>#include<cstdio>#include<deque>#include<utility>#include<vector>usingnamespacestd;typedefpair<int,int>pii;#define REP(i, n) for (int i = 0; i < (n); i++)#define fi first#define mp make_pair#define pb push_back#define se secondintri(){intx;scanf("%d",&x);returnx;}constintN=100000;vector<int>e[N];// {C, {A, B}}// C: whether A covers the parent edge// A: cost of subtree(v)// B: cost of subtree(v)+parent edge; parent edge is the end of some path// A <= B <= A+1pair<bool,pii>dfs(intv,intp){deque<pii>c;intt=-1;boolhas=false;for(autou:e[v])if(u!=p){autor=dfs(u,v);if(!r.fi)has=true;if(r.se.fi==r.se.se)c.push_front(r.se);elsec.pb(r.se);t=u;}if(c.empty())return{false,pii{0,1}};boolcover=false;intf=0,g=0,i=0;for(;i+1<c.size()&&c[i+1].fi==c[i+1].se;i+=2)// beneficial to pair B if the A=B for some childf+=c[i].se+c[i+1].se-1,cover=true;if(i<c.size()){g=f+c[i].se;if(c[i].fi==c[i].se)cover=true;// if A < B for all children and some child is uncoveredf+=!cover&&has?cover=true,c[i].se:c[i].fi;while(++i<c.size())f+=c[i].fi,g+=c[i].fi;}elseg=f+1;// all children are paired, one more edge is needed to cover the parent edgereturn{cover,{f,g}};}intmain(){for(intcc=ri();cc--;){intn=ri();REP(i,n)e[i].clear();REP(i,n-1){intu=ri(),v=ri();e[u].pb(v);e[v].pb(u);}printf("%d\n",dfs(0,-1).se.fi);}}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Repair Roads
You are viewing a single comment's thread. Return to all comments →
C++ Solution