note:This analysis is based on the code of sspa's. You can view it here.2509946 Thanks to lxyxynt && AkemiHomura with helping me understanding the source code.. My iq is really low...

A directed tree is given(N<=3000), the questions is in order to reaches all the nodes in that tree, what's the minimum number of edge(s) to be inversed if at most you can choose two nodes as your original sources(in other words, starting point).

First of all, it's easy to find out for each node, if you arbitaryly select it as the root, how many edges are needed to be inversed in order to traversal all the nodes in the tree just from that root. This process can be done like this: dp[i][j] means if you choose node i as the root, how many edges are have to change direction in order to traversal node j's subtree from node j. So,

clear(dp); 
for(int i=1;i<=n;i++)
	{
		dfs(i,-1,dp[i]);
	}

void dfs(int now,int par,int dp[N])
{
	dp[now]=0;
	for(int k=head[now];k!=-1;k=point[k].next)
	{
		int i=point[k].v;
		if(i==par)
			continue;
		dfs(i,now,dp);
		dp[now]+=dp[i]+point[k].w;
	}
}

After that, a great idea is to enumerate all the edges in the tree. For each edge(assume from u to v), you can imagine if the edge doesn't exist, the tree will be divided into two parts, and the two parts are connected components. Mark the two parts as "left" and "right", so you can choose a starting point(named "l") from the "left" and another starting point(named "r") from "right". Let ret1 as the minimum direction-change operations in order to traversal all the nodes in "left" and "v" from "l", and ret2 as the minimum direction-change operations in order to traversal all the nodes in "right" and "u" from "r". The final answer would be MIN(ret1+ret2-1).

Reason: 1. completeness：as you enumerate all the nodes in that tree, all the condition has been calculated. 2. ret1+ret2-1： if you draw a picture, you can find that ret1 & ret2 cover an single edge——"u to v". So the ret1+ret2 must contains a "0+1" which is cost on the "u to v" edge. However, this edge is actually needn't to be considered as "l" can reaches "v" or "r" can reaches "u" without a change-direction operation. So the plused "1" is redundant. Thus the ans equals to MIN(ret1+ret2-1).

for(int u=1;u<=n;u++)
	{
		for(int k=head[u];k!=-1;k=point[k].next)
		{
			int i=point[k].v;
			int w=point[k].w;
			if(w) continue;
			int ret1=inf; int ret2=inf;
			DFS(i,u,u,ret1); DFS(u,i,i,ret2);
			ans=min(ans,ret1+ret2-1);
		}
	}

void DFS(int now,int p,int a,int & ret)
{
	ret=min(ret,dp[now][now]-dp[now][a]);
	for(int k=head[now];k!=-1;k=point[k].next)
	{
		int i=point[k].v;
		if(i==p) continue;
		DFS(i,now,a,ret);
	}
}

Well, here is something additional: 219D - Choosing Capital for Treeland This is the sub-problem of the one we talked before. You are to find the minimum numbers of inverse operations if only one node can be choosed as the starting point. BUT HERE, n<=200000. The tutorial performed a talented method. You can view it here: Your text to link here... And my code:2251736