【问题描述】
azui大爷厌倦了每天在家颓废的生活，于是开始打工送快递。Jeremy同学不想让azui大爷太轻松，于是想让他送快递的路程尽可能的长。
一句话来说就是：
给出一棵n个点的树，将这n个点两两配对，求所有可行的方案中配对两点间的距离的总和最大为多少。
【输入格式】
一个数n（1<=n<=100,000,n保证为偶数）
接下来n-1行每行三个数x,y,z表示有一条长度为z的边连接x和y（0<=z<=1,000,000,000）
【输出格式】
一个数表示答案。
【样例输入】
6
1 2 1
1 3 1
1 4 1
3 5 1
4 6 1
【样例输出】
7
【样例解释】
（1，2）（3，4）（5，6）分别配对
【数据范围】
对于20%的数据，n <= 14
对于另20%的数据，所给的树是一条链。
对于100%的数据，n <= 100000
第二题看着会感觉很熟悉的样子，很可能会想到最长链等一系列的东西，
但是后来想了很多，也画了很多，有一个错误的思路，然后是一个正确的思路。
先说说错误的。
我想，对于每一个非叶子节点来说，
它下面的子树最好要想办法穿过它，到它的上面去，和上面的点配对。
然后这个点和它的父亲节点之间的边，将会被通过sum[i]次（sum[i]表示以i为根的子树的总结点数（包括i））
然后我把1当做根，跑一遍Dfs。
这个思路是错的，为什么呢，
因为并不能保证所有的点都一定能通过它的父亲节点，
所以有边会被多算，
而且以谁为根也不能确定（不能粗暴地定为1， 退化成链就是例子），
枚举的话会超时。
再说后来想到的正解，
以前上课的时候，听过一个结论，也就是一个证明一样的东西，
对于每条边，它左，右的总结点数，较小的那个会是这条边的贡献（即最多被通过的次数）
就是把较少的那边的点全部跟较多的那边的点配对，
至于为什么一定能配对成功，那就用重心去证明，
重心：以它为根的树最大子树的size最小（比起以其他节点为根）
但是这题我考试的时候还是有问题，虽然后来想出了正解，但是真的一定要注意long long的问题，乘法最好记得开long long，教训阿（直接被某学长的数据砍掉90分）
Code:
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> using namespace std; typedef long long LL; const int Max = 100005; struct node{ int v, len, nxt; }edge[Max << 1]; struct node1{ int l, r, len; }L[Max]; LL Ans; int N, cnt; int sum[Max], fir[Max]; void getint(int & num){ char c; int flg = 1; num = 0; while((c = getchar()) < '0' || c > '9') if(c == '-') flg = -1; while(c >= '0' && c <= '9'){ num = num * 10 + c - 48; c = getchar();} num *= flg; } void addedge(int a, int b, int c){ edge[++ cnt].v = b, edge[cnt].len = c, edge[cnt].nxt = fir[a], fir[a] = cnt; } void Count_P(int r, int fa){ sum[r] = 1; for(int i = fir[r]; i; i = edge[i].nxt) if(edge[i].v != fa){ Count_P(edge[i].v, r); sum[r] += sum[edge[i].v]; } } int main(){ /*int size = 16 << 20; char *p = (char*)malloc(size) + size; __asm__("movl %0, %%esp\n" :: "r"(p));*/ //freopen("pairing.in", "r", stdin); //freopen("pairing.out", "w", stdout); getint(N); int x, y, z; for(int i = 1; i < N; ++ i){ getint(x), getint(y), getint(z); addedge(x, y, z); addedge(y, x, z); L[i].l = x, L[i].r = y, L[i].len = z; } Count_P(1, -1); for(int i = 1; i < N; ++ i){ int t = min(sum[L[i].l], sum[L[i].r]); Ans += (LL)L[i].len * min(N - t, t); } printf("%lld\n", Ans); return 0; }
