【题解】BZOJ 3522/4543 [POI2014]Hotel

请注意,本文编写于 100 天前,最后修改于 100 天前,其中某些信息可能已经过时。

Problem

求树上有多少个三元组 $(u,v,w)$ 满足 $dis(u,v)=dis(v,w)=dis(w,v)$

Thought

对于本题的数据范围,我们可以直接枚举中心,然后对其所有子树暴力求深度为 $d$ 的节点个数,最后做一个组合数

但是在 BZOJ 4543 [POI2014]Hotel加强版 中,显然是不能直接暴力找深度为 $d$ 的节点了

先 Orz 一发出题人

考虑维护一个 $f[x][i]$ 表示当前节点为 $x$ ,子树中和其距离为 $i$ 的节点数目
这个东西很简单的就能够使用长链剖分维护

接着我们考虑每个节点作为三元组 $(u,v,w)$ 的 $lca$ 时的贡献,显然这样计算是不重不漏的

如何计算?

考虑维护 $g[x][i]$ 表示 $x$ 的子树中有多少对点需要与 $x$ 距离为 $i$ 的点进行匹配,成为一个合法的三元组

显然,与 $x$ 距离为 $i$ 的点不能是 $x$ 子树中的点,否则是不合法的

更新答案时:

$g[y][i](y\in son(x))$ 的贡献为 $g[y][i]*f[x][i - 1]$
$g[x][i]$ 的贡献为 $g[x][i]*f[y][i-1](y\in son(x))$

至于 $g[x][i]$ 的更新,首先可以从所有儿子的 $g[y][i+1]$ 处直接转移
然后需要考虑二元组出现在不同子树中的情况,由于其任意两点的 $lca$ 都是 $x$ ,那么需要匹配的点与 $x$ 的距离必然等于它们与 $x$ 的距离

可以在单个子树进行合并的时候直接用 $f[y][i-1]*f[x][i]$ 即为对 $g[x][i]$ 的贡献,同样,这样的二元组也是不重不漏的

由于每个点只有在作为轻儿子时才会被暴力统计,匹配复杂度为 $O(len[x])$ ,并且所有重链长度和为 $n$ ,那么总复杂度是 $O(n)$ 级别的

Ps:注意下标的对应关系

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 100010;
struct Edge {
    int t, n;
}e[N << 1];
int head[N], Etot;

int n;
int len[N], son[N], fa[N];
ll *f[N], *g[N];
ll ans;

void addedge(int u, int v) {
    e[++ Etot] = {v, head[u]};
    head[u] = Etot;
}
void dfs1(int x) {
    for(int i = head[x]; i; i = e[i].n) {
        if(e[i].t == fa[x]) continue;
        fa[e[i].t] = x;
        dfs1(e[i].t);
        if(len[e[i].t] > len[son[x]]) son[x] = e[i].t;
    }
    len[x] = len[son[x]] + 1;
}

void arrange() {
    for(int i = 1; i <= n; ++ i) {
        if(son[fa[i]] != i) {
            f[i] = new ll[len[i] + 1];
            memset(f[i], 0, sizeof(ll) * (len[i] + 1));
            g[i] = new ll[2 * len[i] + 1];
            memset(g[i], 0, sizeof(ll) * (2 * len[i] + 1));
        }
    }
}

void dfs2(int x, ll *F, ll *G) {
    if(son[x])
        dfs2(son[x], F + 1, G - 1);
    for(int i = head[x]; i; i = e[i].n) {
        int t = e[i].t;
        if(t == son[x] || t == fa[x]) continue;
        dfs2(t, f[t], g[t] + len[t] - 1);
        //g[t] + len[t] - 1 = G[0]
        for(int j = 0; j <= len[t]; ++ j) {
            ans += F[j] * g[t][len[t] + j] + G[j + 1] * f[t][j];            
            if(j) G[j] += F[j] * f[t][j - 1];
            G[j] += g[t][len[t] + j];
            if(j) F[j] += f[t][j - 1];
        }
    }
    ans += G[0];
    ++ F[0];
}

int main() {
    n = read();
    for(int i = 1; i < n; ++ i) {
        int u = read(), v = read();
        addedge(u, v);
        addedge(v, u);
    }
    dfs1(1);
    arrange();
    dfs2(1, f[1], g[1] + len[1] - 1);
    printf("%lld\n", ans);
    return 0;
}
Comments

添加新评论