NC544 我们的距离

题目描述

给你一个树，边权都是1，令$dis(i,j)dis(i,j)$dis(i,j)表示$ii$i点和$jj$j点的路径长度，对每个点$ii$i，输出∑j∈(1,n)&&j!=i​dis(i,j)

1. 暴力做法

用Floyd求出所有的$dis(i,j)dis(i,j)$dis(i,j)，直接算。

/**
 * struct Point {
 *	int x;
 *	int y;
 *	Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 点的数量
     * @param edge Point类vector Point.x , Point.y 边所连接的两个点
     * @return long长整型vector
     */
    typedef long long ll;
    
    static const int N = 1000;
    
    int g[N][N];
    
    void floyd(int n) {
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    if (g[i][j] > g[i][k] + g[k][j])
                        g[i][j] = g[i][k] + g[k][j];
    }
    vector<long> solve(int n, vector<Point>& edge) {
        memset(g, 0x3f, sizeof(g));
        
      	// 构造邻接矩阵
        for (auto p : edge) g[p.x][p.y] = g[p.y][p.x] = 1;
        
        floyd(n);
        
        vector<long> res;
        for (int i = 1; i <= n; i++) {
            ll temp = 0;
            for (int j = 1; j <= n; j++) 
                if (i != j) temp += g[i][j]; // 暴力计算dis(i,j)
            res.push_back(temp);
        }
        
        return res;
    }
};

• 时间复杂度：$O\left(n^3\right)O(n^3)$O(n3), floyd算法3重循环。
• 空间复杂度：$O\left(n^2\right)O(n^2)$O(n2). 邻接矩阵存图。

2. 树状dp

方法一时间复杂度太高了，我们分析它有什么冗余的东西。

实际答案只要求输出$\sum dis(i,j)\backslash sum\; dis(i,\; j)$∑dis(i,j)， 并不需要求具体哪一项。所以我们可以关注一下相邻节点的值，看他们有什么关系可以DP。

对于任何一个节点$uu$u, 设他的父节点是$vv$v, 随便在树上取一点$jj$j, 则$dis(u,j)dis(u,\; j)$dis(u,j)和$dis(v,j)dis(v,\; j)$dis(v,j)之差一定为1，不是加1就是减1。那么什么时候+1什么时候减1呢？进一步观察可知，如果$jj$j在$vv$v的子树中，那么$dis(u,j)+1=dis(v,j)dis(u,\; j)+1=dis(v,\; j)$dis(u,j)+1=dis(v,j)，否则$dis(u,j)-1=dis(v,j)dis(u,\; j)-1=dis(v,\; j)$dis(u,j)−1=dis(v,j), 那么我们对所有$jj$j取和，就是题目中的权值$f\left(u\right)f(u)$f(u).

则有公式：

根据上面的推导用$dis(v,j)dis(v,\; j)$dis(v,j)代替$dis(u,j)dis(u,\; j)$dis(u,j), 其中$size\left(u\right)size(u)$size(u)表示$uu$u的子树大小。

因为$jj$j和$j^{\prime }j\text{'}$j′的并集为整个树的所有点，所以两个求和可以合并：

因此得到了计算$f\left(u\right)f(u)$f(u)的dp转移方程。

观察到一个要先算儿子后算父亲，一个是先算父亲后算儿子，因此所以我们必须2次dfs这个树，第一次后序遍历计算$size\left(u\right)size(u)$size(u)并记录，同时计算初值$f\left(1\right)f(1)$f(1), 就是每个点的深度之和，第二次先序遍历计算$f\left(u\right)f(u)$f(u)，最后输出即可。

/**
 * struct Point {
 *	int x;
 *	int y;
 *	Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 点的数量
     * @param edge Point类vector Point.x , Point.y 边所连接的两个点
     * @return long长整型vector
     */
    typedef long long ll;
    
    static const int N = 1e5 + 5;
    
    struct Edge {
        int to, next;
    } e[N << 1];

    int head[N], idx = 1, siz[N];
    vector<long> ans;

    void add_edge(int u, int v) {
        e[idx].to = v;
        e[idx].next = head[u];
        head[u] = idx++;
    }
    void clear_graph() {
        memset(head, -1, sizeof(head));
        memset(e, 0, sizeof(e));
        idx = 1;

        for (int i = 1; i < N; i++) 
            siz[i] = 1;
    }

  	// 计算siz[u]及其孩子
    void dfs1(int u, int f = -1, int dep = 0) {
        ans[0] += dep; // 统计f(1), 其实就是1到当前点的距离，即深度
        
        for (int i = head[u]; ~i; i = e[i].next) {
            int j = e[i].to;
            if (j != f) {
                dfs1(j, u, dep+1); // 后序遍历树，执行完这句后，siz[j]就算完了
                siz[u] += siz[j];
            }
        }
    }
    
    void dfs2(int n, int u, int f = -1) {
        for (int i = head[u]; ~i; i = e[i].next) {
            int j = e[i].to;
            if (j != f) {
              	// 利用前面推导出的公式，计算j点的答案值
                // 下标-1修正
                ans[j-1] = ans[u-1] + n - siz[j] * 2;
              	// 这里需要前序遍历，因为ans[j]依赖的是父亲，需要先算完父亲才能算儿子
              	// 如果递归写上面，会导致u点还没算就继续向下搜j了，那么u点就是错的，后面全错了
                dfs2(n, j, u);
            }
        }
    }
    vector<long> solve(int n, vector<Point>& edge) {
        // write code here
        clear_graph();
        
        ans.resize(n);
        
        for (auto p : edge) {
            add_edge(p.x, p.y);
            add_edge(p.y, p.x);
        }
        
      	// 第一轮深搜，算1号点的权值f(1)和siz数组
        dfs1(1);
      	// 第二轮深搜，基于f(1)和siz算每个点的点权
        dfs2(n, 1);
        
        return ans;
    }
};

• 时间复杂度：$O\left(n\right)O(n)$O(n), 两趟dfs
• 空间复杂度：$O\left(n\right)O(n)$O(n). 前向星存图，边和点都是$nn$n的级别