题目链接：fzu 2038 Another Postman Problem
题目大意：给出n， 然后给出n - 1条边，保证图联通，计算每个点到其他所有点的路径总和的和。
解题思路：一开始想到Floyd算法求出所有点点之间的最短路，但是o(n^3)的复杂度太高了;后来想到说用枚举起点后直接用BFS去计算距离，可是o（n^2)还是超时。后来灵光一闪，发现可以枚举每条边走过的次数，以为图肯定为无环图，所以剪断当前边后，可以将图上的点分为两个集合，然后走过的次数就是两个集合个数的乘积。然后递归遍历每个点的每条边。
#include#include #include #include using namespace std; const int N = 100005; typedef long long ll; struct node { int next; ll val; ll size; node() { next = 0, val = size = 0; }; node(int next, ll val) { this->next = next; this->val = val; this->size = 0; } }; int vis[N]; ll n; vector v[N]; void init() { scanf("%lld", &n); for (int i = 0; i < n; i++) v[i].clear(); memset(vis, 0, sizeof(vis)); int a, b; ll c; for (int i = 1; i < n; i++) { scanf("%d%d%lld", &a, &b, &c); v[a].push_back(node(b, c)); v[b].push_back(node(a, c)); } } ll dfs(int s) { ll cnt = 0; vis[s] = 1; for (int i = 0; i < v[s].size(); i++) { int u = v[s][i].next; if (vis[u]) continue; ll t = dfs(u); v[s][i].size = (n - t) * t; cnt += t; } return cnt + 1; } ll solve() { dfs(0); ll ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < v[i].size(); j++) ans += v[i][j].val * v[i][j].size; } return ans * 2; } int main () { int cas; scanf("%d", &cas); for (int i = 1; i <= cas; i++) { init(); printf("Case %d: %lld\n", i, solve()); } return 0; }