最小距离　题解

Froranzen · 2021-02-04 22:32:09 · 个人记录

题目传送门~

大致题意

给你一棵有 n 个节点的树，有 n - 1 条长度为 x 的边将这 n 个点连接。

请找出一个点，使得当这个点为根节点时，所有点到它的距离之和最小，若有多个答案，请输出最小的节点，同时输出最小距离和。

同时我们规定：每一个点都会被 1 或 0 标记，若当前点 u 的标记为 1 ， 则如果存在一个点 v 到 u 的距离为奇数，那么在统计 u 点为根节点时的距离之和的时候，v 点的贡献将视为 0。 同理，若 u 点的标记为 0 ， 就是到 u 点距离为偶数的点的贡献将视为 0。

思路

1. 首先我们讲一下 O(n^2) 的做法

按照题意，我们对每一个点都进行一次求总距离和的操作。枚举点，时间复杂度为 O(n)，以每个点为根节点遍历树，时间复杂度为 O(n)， 总计 O(n^2)。

至于距离根节点 u 奇偶性的问题，我们只需要判断一下当前点 v 的深度即可：点 v 深度的奇偶性就决定了 v 节点到 u 距离的奇偶性。

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

inline char nc () {
    static char buf[1 << 21], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}

inline int read () {
    register int x(0),f(1);
    char ch = nc ();
    while (ch > '9' || ch < '0') {if (ch == '-') f = ~f +1; ch = nc ();}
    while (ch <= '9' && ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = nc ();}
    return x * f;
}

int n;
const int MAXN = 100005;

struct node {
    int to;
    int next;
    int val;
}e[MAXN << 1];

int head[MAXN << 1], cnt;

void add (int u, int v, int w) {
    e[++cnt] = (node) {v, head[u], w};
    head[u] = cnt;
}

int col[MAXN];
long long qwq[MAXN];
int dep[MAXN];
long long wqw = 0x3f3f3f3f;

void dfs_1 (int u, int fa) {
    for (register int i(head[u]); i; i = e[i].next) {
        int v = e[i].to;
        if (v == fa) continue;
        dep[v] = dep[u] + e[i].val;
        dfs_1 (v, u);
    }
}

void dfs_2 (int root, int u, int fa, int flag) {
    for (register int i(head[u]); i; i = e[i].next) {
        int v = e[i].to;
        if (v == fa) continue;
        if (((flag + e[i].val)% 2) != col[root]) qwq[root] += dep[v];
        dfs_2 (root, v, u, flag + e[i].val);
    }
}

int main () {
    n = read ();
    for (register int i(1); i <= n; ++i) col[i] = read ();
    for (register int i(1); i < n; ++i) {
        int u = read (), v = read (), w = read ();
        add (v, u, w);
        add (u, v, w);
    }
    for (register int i(1); i <= n; ++i) {
        memset (dep, 0, sizeof (dep));
        dfs_1 (i, 0);
        dfs_2 (i, i, 0, 0);
        if (qwq[i] < wqw) wqw = qwq[i];
    }
    for (register int i(1); i <= n; ++i) {
        if (qwq[i] == wqw) {
            printf("%d ", i);
            break;
        }
    }
    printf ("%lld", wqw);
}   

2. 接下来就是重头戏了：O(n) 的换根dp做法

这种题目有一种通法：先求出以 1 为根节点时的距离之和。 之后再一边遍历树，一边利用父亲节点来更新子节点。这样就可以做到 O(n) 解决。

在这里，由于前面的代码和上文的暴力大同小异，我们直接讲树的遍历过程中，父亲节点是如何更新子节点的。

首先，分析父节点 u 和子节点 v 之间的距离，我们容易得出：

若 v 距 u 为偶数距离，则距 v 节点为偶数距离的点，距 u 节点必然为偶数距离，距 v 节点为奇数距离的点，距 u 节点必然为奇数距离。

若 v 距 u 为奇数距离，则距 v 节点为偶数距离的点，距 u 节点必然为奇数距离，距 v 节点为奇数距离的点，距 u 节点必然为偶数距离。

我们首先抛出一个定义 ：

根据上文，在由父亲节点 u 转移到子节点 v 的方程可以先写一点：

如果 u 和 v 间距离为奇数

如果 u 和 v 间距离为偶数

此时，已经初具状态转移的雏形了。不急，我们再来慢慢分析一下 x 和 y 分别是什么。

在上图中，每两个点之间的距离为 1。

我们仔细观察 3 和 6 这两个节点。珂以得出以下结论：

根节点由 3 转移到 6 这个过程中：
1. 6 的子树内所有节点距根节点（也就是6）的距离比当 3 为根节点时全部减去了 3 和 6 之间的距离，也就是1。
2. 6 的子树外所有节点距根节点（也就是6）的距离比当 3 为根节点时全部加上了3 和 6之间的距离，也就是1。

我们再抛出一个定义 ：

这为我们进一步推本题的状态转移提供了基础。

我们进一步猜想：上文的柿子是不考虑距离奇偶性来讲的，那么牵扯到距离的奇偶性后，是不是仍然一样的呢？

大胆猜想：

我们抛出一个定义：