51Nod 1405 树的距离之和(dp)

水深无声 2022-03-30 12:40 224阅读 0赞

[1405 树的距离之和][1405] ![ok.png][]

基准时间限制：1 秒 空间限制：131072 KB 分值: 40 [难度：4级算法题][4]

![star.png][] 收藏

![plus.png][] 关注

给定一棵无根树，如果它有n个节点，节点编号从1到n, 求随意两点之间的距离（最短路径）之和。

Input

第一行包括一个正整数n (n <= 100000)。表示节点个数。
    后面(n - 1)行，每行两个整数表示树的边。

Output

每行一个整数。第i(i = 1,2,...n)行表示全部节点到第i个点的距离之和。

Input演示样例

4
    1 2
    3 2
    4 2

Output演示样例

5
    3
    5
    5

思路：

首先，任选一个节点。设定为树的根。

用num\[x\]表示以节点x为根的子树的节点总数(包括x自身)

假如设定节点1为根。则先求出dp\[1\]，表示全部节点到节点1的距离之和。

对根而言也是全部节点的深度之和。

若x是y的子结点，则有

dp\[x\] = dp\[y\] + (n-num\[x\]) - num\[x\];

由于x为根的子树的全部节点到x的距离比到y的距离少1，所以减num\[x\]

其余节点到x的距离比到y的距离多1，所以加 n-num\[x\]

代码：

#include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #include <vector>
    #pragma comment(linker, "/STACK:10240000,10240000")//递归太深，导致爆栈，所以使用扩栈语句
    using namespace std;
    
    const int N = 100009;
    int dp[N] = {}, num[N];
    vector<int> p[N];
    bool f[N] = {};
    
    void dfs(int s, int depth)
    {
        int len = p[s].size();
        f[s] = 1;
        num[s] = 1;
        dp[1] += depth;
        for(int i=0; i<len; i++)
        {
            if(!f[p[s][i]])
            {
                dfs(p[s][i], depth+1);
                num[s] += num[p[s][i]];
            }
        }
    }
    
    void solve(int s, int n)
    {
        int len = p[s].size();
        f[s] = 1;
        for(int i=0; i<len; i++)
        {
            if(!f[p[s][i]])
            {
                dp[p[s][i]] = dp[s]+n-num[p[s][i]]*2;
                solve(p[s][i], n);
            }
        }
    }
    
    int main()
    {
        int n;
        scanf("%d", &n);
        for(int i=1; i<n; i++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            p[a].push_back(b);
            p[b].push_back(a);
        }
        dfs(1, 0);
        memset(f, 0, sizeof(f));
        solve(1, n);
        for(int i=1; i<=n; i++)
            printf("%d\n", dp[i]);
        return 0;
    }

[1405]: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1405
[ok.png]: http://www.51nod.com/images/icon/ok.png
[4]: http://www.51nod.com/onlineJudge/problemList.html#!groupId=5
[star.png]: http://www.51nod.com/images/icon/star.png
[plus.png]: http://www.51nod.com/images/icon/plus.png