题意： 在一棵n个节点的树上，由于某种原因，树的无向边变成了有向边，这样就不是一个强连通的图了，问最少添加几条特殊路径，能够让树上的任意两点可互相抵达。
特殊路径满足以下几个条件：
- 必须由树上连续的边组成
- 必须是树上有向边的反向边组成
- 一条路径上每个节点最多出现一次
- 多条路径可以有共同的节点和边
思路： 可以知道肯定要使用反向边来填补空缺，使得整个树强连通，所以一定要使用n-1条反向边。显而易见，因为不存在环，树上每个节点到其他节点有且仅有一条路径。
所以要处理每一个节点的边的情况。
使用num数组来记录在某节点之下使用反向边向下的路径条数，负数表示使用反向边向上。
每次传递都遵循以下原则：
- 如果反向边的传递方向相同，直接将孩子的路径条数加在父节点上。
- 如果传递方向不同，那么就减少父节点所储存的路径条数，并把先能计算的路径条数算在结果里。
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <string>
#include <math.h>
#include <bitset>
#include <ctype.h>
using namespace std;
typedef pair<int,int> P;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-9;
const int N = 25000 + 5;
const int mod = 1e9 + 7;
int t,kase = 0;
vector<P> G[N];
int ans = 0;
int vis[N], num[N];
int dfs(int u)
{
vis[u] = 1;
for(int i = 0; i < G[u].size(); i++)
{
int v = G[u][i].first, type = G[u][i].second;
if(vis[v]) continue;
dfs(v);
if(type == 1)
{
if(num[v] < 0)
{
num[u] += num[v];
}
else
{
ans += abs(num[v]) + 1;
num[u]--;
}
}
else if(type == -1)
{
if(num[v] > 0)
{
num[u] += num[v];
}
else
{
num[u]++;
}
}
}
}
int n;
int main()
{
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
for(int i = 0; i < N; i++) G[i].clear();
for(int i = 0; i < n-1; i++)
{
int u,v;
scanf("%d%d", &u, &v);
G[v].push_back(make_pair(u,-1));
G[u].push_back(make_pair(v, 1));
}
memset(num, 0, sizeof(num));
memset(vis, 0, sizeof(vis));
ans = 0;
dfs(0);
if(num[0] > 0)
ans += num[0];
printf("Case %d: %d
", ++kase, ans);
}
return 0;
}