2020-9-29 T3

题意：给定一颗大小为 \(n(n \le 5 \times 10 ^ 4)\) 的树，保证树的生成方式随机，你需要选定两个点 \(x, y\)，最小化：

\[\sum\limits_{i = 1} ^ n a_i \times \min(dis_{x, i}, dis_{y, i})
\]

你会发现这个问题很类似 [APIO2015]八邻旁之桥，那么同样的我们可以先思考只有单点的情况。

即考虑如何选定 \(x\) 最小化：

\[\sum\limits_{i = 1} ^ n a_i \times dis_{x, i}
\]

那么是不是只要能快速算出每个点 \(x\) 的 \(w_x = \sum\limits_{i = 1} ^ n a_i \times dis_{x, i}\) 即可呢？

来尝试一下，因为树高是 \(\log n\) 的，因此我们要尽可能地使用和树高有关的做法。

那么根据两点之间的距离公式 \(dis_{x, i} = dep_{x} + dep_i - 2 \times dep_{lca}\)，显然 \(dep_x\) 是固定的。

其中最难处理的就是 \(dep_{lca}\) 了，因此我们要想办法固定住 \(dep_{lca}\)。

结合之前树高是 \(\log n\) 的性质，不难发现我们可以一步步向上跳，将每次跳到的点记为 \(y\)。

如果此时 \(y\) 是 \(lca_{x, i}\)，显然 \(i\) 就应该是除了 \(x\) 所在子树以外的所有点。

那么那么此时这些点 \(i\) 到 \(x\) 的距离就是其到 \(y\) 的距离在加上 \(y\) 到 \(x\) 的距离。

这部分多与的距离很好维护，直接令 \(S_x = \sum\limits_{i \in x} a_i\)，然后减一下乘距离即可。

那么这些点到 \(y\) 的距离怎么维护呢，不难发现实际上这是 \(y\) 的整颗子树到其距离减去 \(x\) 所在子树到 \(y\) 的距离即可。

那么就只需要维护 \(f_x = \sum\limits_{i \in x} a_i \times dis_{x, i}\) 以及 \(g_x = \sum\limits_{i \in x} a_i \times dis_{i, fa_x}\)，即可。

上面这两个值通过子树合并即可计算。

通过最开始的流程，不难发现 \(w_x\) 的计算方法。

值得一提的是，上面这个做法本质上使用的是点分治的思想。

那么现在一维的情况已经解决，可以来考虑二维的情况。

和最开始提到的那道题很类似的是，对于选定的两个点 \(x, y\) 一定是从这条链的中点分开一部分全部走去 \(x\)，另一部分全部走去 \(y\)。

那么我们可以类似与那道题的做法，断去树中的一条边，两边的树就只需要跑上面哪个一维的子问题了。

但是你会发现的是，如果我们继续重新对两边重新计算 \(w_x\)，复杂度还是 \(O(n ^ 2)\) 的，同样的我们还是希望能找到一个和树高有关的做法。

可以继续沿用上面递推的思想，看一看能否先计算出一个点的 \(w_x\) 然后沿着树边往下递推。

可以考虑一个简单的情况，如果 \(x\) 往其一个儿子 \(y\) 走 \(w_y\) 的变化情况。

不难发现会有：\(w_y = w_x + S - 2 \times S_y, S\) 为整颗树的权值和。

那么如果 \(w_y\) 会变小当且仅当 \(S - 2 \times S_y < 0\)，移项可得：\(S_y > \frac{S}{2}\)。

可以惊奇地发现对于显然这样的 \(y\) 只会存在一个。

那么如果存在这样的点 \(y\) 就一定可以从当前的根已知往下走直到 \(S - 2 \times S_y > 0\) 为止。

可以发现上述这个过程在数随机生成的情况下是可以保证为 \(O(\log n)\) 的。

那么现在的任务就在于如何计算出一个断边 \((u, v)(fa_v = u)\) 后的 \(w_u, w_v\) 即可。

不难发现有 \(w_v = f_v, w_u = w_u - g_v\)。

并且可以发现断边以后将 \(u\) 做为新树的根只会影响 \(u\) 到根路径上的点的 \(S\) 值，直接暴力修改即可。

于是我们就在 \(O(n \log n)\) 的复杂度下完成了本题，事实上从大佬哪里听说貌似使用动态点分治就可以不依赖于树随机生成的性质，以后学习了动态点分治再说吧。

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define rep(i, l, r) for (int i = l; i <= r; ++i)

#define Next(i, u) for (int i = h[u]; i; i = e[i].next)

const int N = 50000 + 5;

const int inf = 1e18;

struct edge {

    int v, next;

}e[N << 1];

int n, u, v, tot, top, ans = inf, cnt1, cnt2, h[N], a[N], f[N], g[N], w[N], S[N], fa[N], st[N], dep[N];

int read() {

    char c; int x = 0, f = 1;

    c = getchar();

    while (c > '9' || c < '0') { if(c == '-') f = -1; c = getchar();}

    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

void add(int u, int v) {

    e[++tot].v = v, e[tot].next = h[u], h[u] = tot;

    e[++tot].v = u, e[tot].next = h[v], h[v] = tot;

}

void dfs(int u, int fa, int topf) {

    f[topf] += (dep[u] - dep[topf]) * a[u];

    Next(i, u) if(e[i].v != fa) dfs(e[i].v, u, topf);

}

void Prefix(int u, int Fa) {

    S[u] = a[u], dep[u] = dep[Fa] + 1, fa[u] = Fa;

    Next(i, u) if(e[i].v != Fa) Prefix(e[i].v, u), S[u] += S[e[i].v];

    dfs(u, Fa, u), g[u] = f[u] + S[u], w[u] = f[u];

}

void access(int u, int fa, int &cnt, int tmp, int topf) {

    cnt = tmp;

    Next(i, u) {

        int v = e[i].v; if(v == fa) continue;

        if(S[topf] - 2 * S[v] < 0) access(v, u, cnt, tmp + S[topf] - 2 * S[v], topf);

    }

}

void solve(int u, int Fa) {

    Next(i, u) {

        int v = e[i].v; if(v == Fa) continue;

        st[u] = S[u], S[u] = S[1] - S[v];

        for (int j = fa[u], k = u; j; k = j, j = fa[j]) st[j] = S[j], S[j] = S[1] - st[k];

        access(v, u, cnt1, f[v], v), access(u, v, cnt2, w[u] - g[v], u);

        for (int j = u; j; j = fa[j]) S[j] = st[j];

        ans = min(ans, cnt1 + cnt2), solve(v, u);

    }

}

signed main() {

    n = read();

    rep(i, 1, n - 1) u = read(), v = read(), add(u, v);

    rep(i, 1, n) a[i] = read();

    Prefix(1, 0);

    rep(i, 1, n) for (int j = i; fa[j]; j = fa[j]) {

        w[i] += f[fa[j]] - g[j] + (dep[i] - dep[fa[j]]) * (S[fa[j]] - S[j]);

    }

    solve(1, 0);

    printf("%lld", ans);

    return 0;

}

值得一提的是，当树高期望为 \(\log n\) 时，一个很好运用性质的方式就是从叶子开始往上递推或者从上往下递推。

巴特西

2020-9-29 T3

最新文章

热门文章