Codeforces 219 D. Choosing Capital for Treeland

Problem Statement:

http://codeforces.com/problemset/problem/219/D

Approach : Simple DFS.

For Node 4 : No. of downward arrows in path from 1 + No. of upward arrows in rest of the tree except the path

0 + 2

2
This is same for Node 2,3 as well :)


Solution :

#include<bits/stdc++.h>
using namespace std ;
//-------------------------------
typedef long long ll ;
typedef vector vi ;
typedef pair<int,int> ii ;
//-------------------------------
#define _CRT_SECURE_NO_WARNINGS
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define rep(i,a,b) for(ll i=(a) ; (i)<(b) ; ++i)
#define inf 2000000000
#define endl "\n"
#define de(x) cerr<<#x<<" is "<<x<<endl; #define max(a,b) ( (a>b) ? (a) : (b) )
#define min(a,b) ( (a<b) ? (a) : (b) )
//------------------------------
int ri() { char c = getchar(); while(c<'0' || c>'9') c=getchar(); int ret = 0; while(c>='0' && c<='9') { ret=10*ret+c-48; c=getchar(); } return ret; }
const int maxn=2e5+5;
map< ii , int>up,down,mo;
int ans[maxn];
vi gr[maxn];
int ap=0,dwn=0;
int u,v,m;
void dfs1(int x,int pa)
{
rep(i,0,gr[x].size())
{
u=gr[x][i] ;
if(u==pa) continue ;
if(mo[mp(x,u)])
{
up[mp(x,u)]=1;
ap++;
}
else
{
down[mp(x,u)]=1;
dwn++;
}
dfs1(u,x);
}
}
int mx=inf;
void dfs2(int x,int pa,int cur_up, int tot)
{
rep(i,0,gr[x].size())
{
u=gr[x][i];
if(u==pa) continue ;
dfs2(u,x,cur_up+up[mp(x,u)],tot+1);
}
int cur = 2*cur_up + dwn - tot;
mx = min(cur,mx);
ans[x]=cur;
}
int main()
{

scanf("%d",&m);
m--;
rep(i,0,m)
{
scanf("%d%d",&u,&v);
gr[u].pb(v);
gr[v].pb(u);
mo[mp(u,v)]=1;
}
dfs1(1,-1);
dfs2(1,-1,0,0);
cout << mx << endl ;
rep(i,1,m+2) if(ans[i]==mx)
cout << i << " " ;
}