问题2797--树上的最值(treegb)

2797: 树上的最值(treegb)

时间限制: 1 Sec  内存限制: 128 MB
提交: 12  解决: 10
[提交] [状态] [讨论版] [命题人:]

题目描述

有2*n个点构成一棵树,BSNY要将他们分成n组,每组2个点。
BSNY想知道如何分组,可以使得每组内两个点距离之和最小,同时BSNY还想知道如何分组,可以使得每组内两个点距离之和最大。
例如样例第一个数据中有3组,共6个点,分组方式{1, 4} {5, 6} {2, 3},距离和最小,为15;分组方式{1, 4} {2, 6} {3, 5},距离和最大,为33。
注意,每个点巧好分到一组。
WINDOWS下手工开栈加下面几句话,注意提交时注释或去掉
int size = 256 << 20; // 256MB
char *p = (char*)malloc(size) + size;
__asm__("movl %0, %%esp\n" :: "r"(p));

输入

第一行输入T,表示有T个测试数据
每个测试数据第一行输入n,接下来2*n-1行输入树的边的信息a, b, c,表示a和b之间有长度c的边。

输出

对于每个测试数据,输出最小和最大距离和,空格隔开。

样例输入 Copy

2
3
1 2 3
3 2 4
2 4 3
4 5 6
5 6 5
2
1 2 1
1 3 2
1 4 3

样例输出 Copy

15 33
6 6

提示

30%数据 1<=n<=10
50%数据 1<=n<=1000
另有10%数据  树是一条链
100%数据 1<=n<=100000    1<=a, b<=2*n   1<=c<=10^6   1<=T<=50

来源/分类