6504: BZOJ2504：间谍

作为一名间谍，你的任务是确定国家之间运送的货物。每箱货物在驶离出口国后，都会被导向至少一个中间港口。在所有的港口，货物都储存在仓库之中，所以你没法从出口国到进口国追踪特定的箱子。卫星照片告诉你每条航道上每个方向运输了多少箱货物。同时你还知道这些箱子都走最短路。

你的任务是确定指定的两个国家之间的最大可能货运量和最小可能货运量，以箱数记。货运网络可以看作是一棵无根树，其中国家是叶子节点，中间港口是中间节点。同时你了解到，每箱货物一旦到达离开港口，绝对不会折返原路。

如上图所示，有6个国家，标号为1,2,4,5,7,9，还有三个港口，标号为3,6,8。虽然从1号国家到4号国家的路径上的每条边都通过了至少4箱货物，但是实际上没法从1号国家到4号国家输送4箱货物。非要如此，则在6号港口会有1箱从2号国家的送来的货物被迫折返，如是不可。

输入格式

       输入的第一行有一个整数n (3 <= n <= 10000)：节点个数（包括了国家和中间港口）。

之后的n-1行每行有四个整数a, b, c1, c2 (1 <= a, b <= n and 0 <= c1, c2 <= 1000)，表示从a到b的航道上有c1箱货物，从b到a的航道上有c2箱货物。

最后一行是两个整数fr和to (1 <= fr, to <=n, fr != to)：指定的两个国家，分别是出口国和进口国。

每行的整数由单个空格隔开。输入数据满足Kirchhoff定律：在每个港口输入的箱数等于输出的箱数。虽说满足此定律并不意味着必然存在一个输出方案满足输入的描述，但是，输入数据经过特殊设计，确保至少一个方案的存在性。

输出格式

       输出一行，包括两个由单个空格分隔开的整数，分别为从fr到to的最小和最大可能运输箱数，要求满足给定的数据。

样例输入

9

1 6 4 1

2 6 2 1

6 3 4 0

7 3 1 1

9 3 1 1

3 8 6 2

8 4 4 1

8 5 2 1

1 4

样例输出

1 3

【数据规模和约定】
50%的数据中n≤10；
100%的数据中n≤10000。

 

提示

没有写明提示

题目来源

2011福建集训