51nod 1405 树的距离之和 【dfs--记忆dp??树形dp??】

第一行包含一个正整数n (n <= 100000)，表示节点个数。后面(n - 1)行，每行两个整数表示树的边。Output
每行一个整数，第i(i = 1,2,...n)行表示所有节点到第i个点的距离之和。Input示例
41 23 24 2Output示例
5355曹鹏 (题目提供者)
题解：
先定义四个概念--
lower_sum 表示此点的全部孩子到此点的距离之和。dian_sum为此点和孩子点的总个数。border_sum 为 非此点孩子的节点到此点的距离之和。
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为此点和孩子点的总个数，    border_sum 为 非此点孩子的节点到此点的距离之和。 */}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;}
另外附一个求书上任意两点之和的求解方法-.- （我开始把题意理解成了这个问题---写好看了样例发现不是这个问题  -.-  wwwwwww ）.
即考虑每条边的利用率----
每条边的利用率为此边下方的点个数N * 此边上方的点个数 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;}