第一行包含一個正整數(shù)n (n <= 100000)，表示節(jié)點個數(shù)。后面(n - 1)行，每行兩個整數(shù)表示樹的邊。Output
每行一個整數(shù)，第i(i = 1,2,...n)行表示所有節(jié)點到第i個點的距離之和。Input示例
41 23 24 2Output示例
5355曹鵬 (題目提供者)
題解：
先定義四個概念--
lower_sum 表示此點的全部孩子到此點的距離之和。dian_sum為此點和孩子點的總個數(shù)。border_sum 為 非此點孩子的節(jié)點到此點的距離之和。
ans_sum 為此點到所有點之和。
然后第一編dfs求解lower_sum 和 dian_sum  
第二遍dfs求解 border_sum 和 ans_sum
代碼：
//每個邊的利用率為 n *  m ----   總和  --#include<stdio.h>#include<string.h>#include<vector>#include<iostream>#include<algorithm>using namespace std;#define LL long longvector<int> V[100100];struct node{    LL lower_sum,dian_sum,border_sum,ans_sum;/*    lower_sum 表示此點的全部孩子到此點的距離之和，    dian_sum為此點和孩子點的總個數(shù)，    border_sum 為 非此點孩子的節(jié)點到此點的距離之和。 */}pp[100100];LL ans;int n;void dfs_one(int x,int f){    pp[x].dian_sum=1;    for (int i=0;i<V[x].size();i++)    {        int v=V[x][i];        if (v==f) continue;        dfs_one(v,x);        pp[x].lower_sum+=pp[v].dian_sum+pp[v].lower_sum;        pp[x].dian_sum+=pp[v].dian_sum;    } //   cout<<x<<' '<<pp[x].dian_sum<<' '<<pp[x].lower_sum<<' '<<pp[x].border_sum<<endl;}void dfs_two(int x,int f){    if (f!=-1)    {        pp[x].border_sum=pp[f].border_sum+pp[f].lower_sum+n-2*pp[x].dian_sum-pp[x].lower_sum;        pp[x].ans_sum=pp[x].border_sum+pp[x].lower_sum;    }    else    pp[x].ans_sum=pp[x].lower_sum;  //  cout<<x<<' '<<pp[x].dian_sum<<' '<<pp[x].lower_sum<<' '<<pp[x].border_sum<<' '<<pp[x].ans_sum<<endl;    for (int i=0;i<V[x].size();i++)    {        int v=V[x][i];        if (v==f) continue;        dfs_two(v,x);    }}int main(){    int a,b;    cin>>n;    for (int i=1;i<n;i++)    {        cin>>a>>b;        V[a].push_back(b);        V[b].push_back(a);    }    ans=0;    memset(pp,0,sizeof(pp));    dfs_one(1,-1);  //  cout<<"/n/n"<<endl;    dfs_two(1,-1);//    cout<<ans<<endl;    for (int i=1;i<=n;i++)        cout<<pp[i].ans_sum<<endl;    return 0;}
另外附一個求書上任意兩點之和的求解方法-.- （我開始把題意理解成了這個問題---寫好看了樣例發(fā)現(xiàn)不是這個問題  -.-  wwwwwww ）.
即考慮每條邊的利用率----
每條邊的利用率為此邊下方的點個數(shù)N * 此邊上方的點個數(shù) M   * 2  -----   即下方到上方  和 上方到下方-----
代碼：
//每個邊的利用率為 n *  m ----   總和  --#include<cstdio>#include<cstring>#include<vector>#include<iostream>#include<algorithm>using namespace std;#define LL long longvector<int> V[100100];LL ans;int n;int dfs(int x,int f){    int he=1,k;    for (int i=0;i<V[x].size();i++)    {        if (V[x][i]==f)            continue;        k=dfs(V[x][i],x);        ans+=k*(n-k)*2;        he+=k;    }    return he;}int main(){    int a,b;    cin>>n;    for (int i=1;i<n;i++)    {        cin>>a>>b;        V[a].push_back(b);        V[b].push_back(a);    }    ans=0;    dfs(1,-1);    cout<<ans<<endl;    return 0;}