题目
点这里看题目。
分析
这道题......第一眼以为是和 [CF1025G]Company Acquisitions 相似的题目。
最后发现它们确实很像......仅限于思考方向，实际方法完全不同。
本题中，由于树是二分图，因此我们可以对它进行黑白染色。对于菊花图，某种颜色只出现在一个点上。因此，我们要考虑操作的颜色数量的影响。
不难发现，一次操作会且仅会令一种颜色出现次数减少 1 ，另一种增加 1 ：
- 当我们将 (a) 连向 (c) 的时候，它的颜色会改变；
- 当我们将 (a) "子树"连向 (c) 的时候，它们的颜色都不会改变；
......所以......我们只需要统计每种颜色的出现次数，并且决定最终是哪种颜色出现在根就行了。具体而言，我们直接染色，然后数一下每种颜色各自的出现次数，最后计算输出即可。
小结：
这些题实际上都是在考虑将图整体量化为一个指标，并且分析操作对这个指标的影响，最终求解（往往求解的时候毫无难度，难度全在思考上了(╯‵□′)╯︵┻━┻）。
至于怎么把图化成指标......见仁见智吧。入手点在于操作的特点，或许可以帮助你反推出它？
代码
#include <cstdio>
const int MAXN = 2e5 + 5;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
template<typename _T>
_T MIN( const _T a, const _T b )
{
return a < b ? a : b;
}
struct Edge
{
int to, nxt;
}Graph[MAXN << 1];
int tot[2];
int head[MAXN];
int N, cnt;
void AddEdge( const int from, const int to )
{
Graph[++ cnt].to = to, Graph[cnt].nxt = head[from];
head[from] = cnt;
}
void DFS( const int u, const int fa, const int dep )
{
tot[dep & 1] ++;
for( int i = head[u], v ; i ; i = Graph[i].nxt )
if( ( v = Graph[i].to ) ^ fa )
DFS( v, u, dep + 1 );
}
int main()
{
read( N );
for( int i = 1, a, b ; i < N ; i ++ )
read( a ), read( b ), AddEdge( a, b ), AddEdge( b, a );
DFS( 1, 0, 0 );
write( MIN( tot[0] - 1, tot[1] - 1 ) ), putchar( '
' );
return 0;
}