问题描述

一道编程题，用c++编程，求助

给定一颗无根树，假设它有n个节点，节点编号从1到n，求任意两点之间的距离之和，也就是求任意一点到其它点的距离之和，边长都为1。要求时间复杂度为O(n)

解决方案

先做一遍DFS求出所有节点到根节点的距离之和，然后可以发现，如果知道到一个点的距离之和，可以用O(1)求出所有节点到它相邻点的距离之和

解决方案二：

 /* ***********************************************Author        :xdloveCreated Time  :2016年05月17日 星期二 07时12分25秒File Name     :2016_05_17_51nod_1405.cpp************************************************ */#pragma comment(linker/STACK:102400000102400000"")#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>#include <memory.h>#include <vector>#include <queue>#include <set>#include <map>#include <string>#include <math.h>#include <stdlib.h>#include <time.h>using namespace std;const int N = 1e5 + 10;long long son[N]val[N];long long ans[N];struct Edge{    int vnext;}edge[N << 1];int head[N]tot;int n;void init(){    tot = 0;    memset(head-1sizeof head);}void addedge(int uint v){    edge[tot].v = v;    edge[tot].next = head[u];    head[u] = tot++;}void dfs(int uint pre){    son[u] = 1;    val[u] = 0;    for(int i = head[u]; i != -1; i = edge[i].next)    {        int v = edge[i].v;        if(v != pre)        {            dfs(vu);            son[u] += son[v];            val[u] += son[v] + val[v];        }    }}void dfsAgain(int uint pre){    ans[u] = val[u];    for(int &i = head[u]; i != -1; i = edge[i].next)    {        int v = edge[i].v;        if(v != pre)        {            long long tp = val[u] - val[v] - son[v];            val[v] += n - son[v] + tp;            dfsAgain(vu);        }    }}void solve(){    init();    cin >> n;    for(int i = 1; i <= n - 1; ++i)    {        int uv;        scanf(""%d %d""&u&v);        addedge(uv);        addedge(vu);    }    dfs(1-1);    dfsAgain(1-1);    for(int i = 1; i <= n; ++i)        printf(""%lld
""ans[i]);}int main(){    //freopen(""in.txt""r""stdin);    //freopen(""out.txt""w""stdout);    solve();     return 0;}

解决方案三：
【求助】一道考验脑细胞的编程题