CCF-CSP认证考试 202212-4 聚集方差 100分题解

更多 CSP 认证考试题目题解可以前往：CSP-CCF 认证考试真题题解

原题链接： 202212-4 聚集方差

时间限制： 2.0s
内存限制： 512.0MB

问题背景

通常而言，对一组数据 $A={a_1,...,a_n}$ ，可以使用方差 $\sigma^2(A)=\frac 1n\sum_{i=1}^n (a_i-\mu(A))^2$ 来衡量其离散程度（其中 $\mu(A)=\frac{1}{n}\sum_{i=1}^na_i$ 为平均值），或者说“整体聚集”的程度。然而，现实生活中的数据有时是“分组聚集”的——它们可以被分为若干组，每一组都是相对“聚集”的，但不同组间差距较大，因此整体相对离散。此时，方差无法反映这种分组聚集的性质，而人为指定分组的情况则使计算复杂。为此，可以提出一种简单的衡量方式：称一组数据 $A={a_1,a_2,...,a_n}$ 的“聚集方差”为：
$\mathcal G(A)=\frac 1n\sum_{i=1}^n \min_{j=1,j\neq i}^n (a_i-a_j)^2$
特别的，当 $n = ∣ A ∣ = 1$ 时，规定 $\mathcal G(A)=0$ 。

例如，对 $A={0,0,0,4,4,4,7,8,9}$ ，则方差 $\sigma^2(A)=\frac{98}{9}\simeq10.89$ ，但 $\mathcal G(A)=\frac{1}{3}\simeq 0.33$ ，说明若 $A$ 按 ${0,0,0},{4,4,4},{7,8,9}$ 的方式分组，则相对与整体而言，每一组内都相对聚集。

问题描述

考虑这样一个模型：现实中一个公司的结构可以用一棵有根树来描述，其中每个点对应一位员工，其父节点（如果有的话）代表了他的直属上司，而其自子树中的点（包括这个点本身）则代表所有可被他支配的员工（广义的讲，人可以支配自己，因此人可以视为自己的员工，因此此处“员工”的概念包括他自己本人）。

一般地，假定该公司内有 $n$ 位员工，编号从 $1$ 到 $n$ ；对编号为 $x$ 的员工，记 $T (x)$ 为其子树内所有点的编号的集合（包括 $x$ 本身）。

对 $x > 1$ ，记 $p_x$ 为其父节点的编号，并假定总有 $1\le p_x<x$ （从而编号为 $1$ 的员工是该公司唯一的老板）。

我们说明“聚集方差”可以作为一种统计方式帮助该公司的老板了解他的公司，例如，假定每个员工每年都有一小时的可以自主选择时间的带薪年假，那么可以根据历史数据，统计出每位员工偏好的时间；对第 $x\in[1,n]$ 位员工，可以用一个非负整数 $a_x$ 表示其偏好的时间。

记 $A(x)={a_y:y\in T(x)}$ 为编号为 $x$ 的点的子树内所有点（包括 $x$ ）对应员工的偏好时间的可重集合（从而 $∣ A (x) ∣ = ∣ T (x) ∣$ ）。那么，对于一位编号为 $x$ 的员工，若其可支配的员工偏好的时间的聚集方差 $\mathcal G(A(x))=\frac{1}{|T(x)|}\sum_{y\in T(x)}\min_{z\in T(x),z\neq y}(a_z-a_y)^2$ 较小，那么说明他可能需要担心会因在某个时间有较多的员工请假而导致工作任务受到影响，从而应该调整工作日程以避免这一问题；反之则说明他不太需要过多关注这一点。

因此该公司的老板想了解，对每个 $x\in[1,n]$ ， $\mathcal G(A(x))$ 是多少？当然，为了避免精度误差，你只需要输出 $\text{Ans}_x=|T(x)|\mathcal G(A(x))$ 。容易验证 $\text{Ans}_x$ 总是整数。

输入格式

从标准输入读入数据。

第一行一个正整数 $n$ 表示树的大小；

接下来一行 $n - 1$ 个正数依次表示 $p_2,...,p_n$ ；

接下来一行 $n$ 个非负数依次表示 $a_1,...,a_n$ 。

输出格式

输出到标准输出中。

$n$ 行，其中第 $i$ 行为一个非负整数表示 $\text{Ans}_i$ 。

样例输入

2
1
0 1

样例输出

2
0

评测用例规模与约定

子任务编号	$n\le$	特殊性质	子任务分值
$1$	$300$	/	$15$
$2$	$3000$	/	$25$
$3$	$300000$	A	$15$
$4$	$300000$	B	$15$
$5$	$300000$	C	$10$
$6$	$300000$	/	$20$

特殊性质 A： $\forall i\in(1,n],p_i=i-1$ ；

特殊性质 B： $\forall i\in(1,n],p_i=\left\lfloor\frac i2\right\rfloor$ ；

特殊性质 C： $\forall i,j\in[1,n],i\neq j\Rightarrow a_i\neq a_j$ 。

对于 $100\%$ 的数据， $2\le n\le 3\times 10^5;\forall i\in(1,n],p_i\in[1,i);\forall i\in[1,n],a_i\in[0,10^9]$ 。

题解

启发式合并。

对于每个子树 $u$ ，用 std::map<int, pair<int, int>> 表示在这棵子树中，偏好时间为 $a_i$ 的人所对应的最小的 $\min_{j\in T(u),j\neq i}(a_j-a_i)^2$ 的 $a_j$ 的值，以及偏好时间为 $a_i$ 的人的数量（下文会简写为 $c n t$ ）。

当 $c n t > 1$ 时，易知 $a_j=a_i$ ，此时 $\min_{j\in T(u),j\neq i}(a_j-a_i)^2=0$ 。

考虑启发式合并的过程：这里我是先将当前子树的根的 map 作为引用参数通过 dfs 求出重儿子的信息，然后将当前子树的根插入，最后求出所有的轻儿子的信息并向根的 map 中逐元组合并。

对于每一次向 map 中插入元组 $a_i,a_j,cnt)$ ，可以看成在数轴上插入一个点 $a_i$ ，然后去更新距离每个点最近的点，可以发现受影响的只有小于 $a_i$ 的最大的元组 $pre.a_i,pre.a_j,pre.cnt)$ 、大于 $a_i$ 的最小元组 $suf.a_i,suf.a_j,suf.cnt)$ 和当前元组。

对于每次插入操作，考虑两种情况：

原先有相同键值的元组 $a_i,A_j,CNT)$ ，此时插入后必定使 $a_i$ 键值的 $c n t > 1$ ， $A_j$ 应该等于 $a_i$ ，那么就可以让 $ans-=A_j^2*cnt$ 来消去原先对答案的影响，并将 $A_j$ 设为 $0$ ， $CNT$ 加上 $c n t$ 。这样如果在合并一个键值为 $a_i$ 的元组只会减 $0$ ，不会产生影响。
原先没有相同键值的元组，此时 $p re, s u f$ 的值都有可能会更新：
1. 先将原先的值从答案中减去，即 $ans-=(pre.a_j)^2\times pre.cnt+(suf.a_j)^2\times suf.cnt$ ；
2. 更新 $p re, s u f$ 元组，即 $pre.a_j=\min\{pre.a_j,a_i-pre.a_i\}$ ， $suf.a_j=\min\{suf.a_j,suf.a_i-a_i\}$ ；
3. 将 $p re, s u f$ 对答案的影响加回去，即 $ans+=(pre.a_j)^2\times pre.cnt+(suf.a_j)^2\times suf.cnt$ ；
4. 插入元组的值 $a_i,\min\{a_i-pre.a_i,suf.a_i-a_i\},cnt)$ ，并计算该值对答案的影响，即 $ans+=(\min\{a_i-pre.a_i,suf.a_i-a_i\})^2\times cnt$ 。

为了方便写，将叶子结点的 $a_j$ 设为 $+\infty$ ，对应的答案设为 $(+\infty)^2$ ，在输出时特判即可，否则取 $\min$ 的时候要单独考虑叶子结点。

时间复杂度： $\mathcal{O}(n\log^2n)$ 。

参考代码（953ms，99.19MB）

/*
    Created by Pujx on 2024/3/28.
*/
#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
//#define double long double
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
#define inf (int)0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define yn(x) cout << (x ? "yes" : "no") << endl
#define Yn(x) cout << (x ? "Yes" : "No") << endl
#define YN(x) cout << (x ? "YES" : "NO") << endl
#define mem(x, i) memset(x, i, sizeof(x))
#define cinarr(a, n) for (int i = 1; i <= n; i++) cin >> a[i]
#define cinstl(a) for (auto& x : a) cin >> x;
#define coutarr(a, n) for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n]
#define coutstl(a) for (const auto& x : a) cout << x << ' '; cout << endl
#define all(x) (x).begin(), (x).end()
#define md(x) (((x) % mod + mod) % mod)
#define ls (s << 1)
#define rs (s << 1 | 1)
#define ft first
#define se second
#define pii pair<int, int>
#ifdef DEBUG
    #include "debug.h"
#else
    #define dbg(...) void(0)
#endif

const int N = 3e5 + 5;
//const int M = 1e5 + 5;
const int mod = 998244353;
//const int mod = 1e9 + 7;
//template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }
//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }

int a[N];
int n, m, t, k, q;
int fa[N], son[N], sz[N];
vector<int> g[N];

void dfs(int u) {
    sz[u] = 1;
    for (auto v : g[u]) {
        dfs(v);
        sz[u] += sz[v];
        if (!son[u] || sz[v] > sz[son[u]]) son[u] = v;
    }
}

i64 ans[N];
void add(int u, int val, int cnt, map<int, pii>& mp) {
    if (mp.count(val)) {
        auto& cur = mp[val];
        ans[u] -= 1ll * cur.ft * cur.ft * cur.se;
        cur.ft = 0, cur.se += cnt;
    }
    else {
        mp[val] = {inf * (cnt == 1), cnt};
        auto& cur = mp[val];
        auto it = mp.lower_bound(val);
        if (it != mp.begin()) {
            --it;
            auto& pre = it->se;
            cur.ft = min(cur.ft, val - it->ft);
            if (pre.se) {
                ans[u] -= 1ll * pre.ft * pre.ft * pre.se;
                pre.ft = min(pre.ft, val - it->ft);
                ans[u] += 1ll * pre.ft * pre.ft * pre.se;
            }
        }
        it = mp.upper_bound(val);
        if (it != mp.end()) {
            auto& suf = it->se;
            cur.ft = min(cur.ft, it->ft - val);
            if (cur.se) {
                ans[u] -= 1ll * suf.ft * suf.ft * suf.se;
                suf.ft = min(suf.ft, it->ft - val);
                ans[u] += 1ll * suf.ft * suf.ft * suf.se;
            }
        }
        ans[u] += 1ll * cur.ft * cur.ft * cur.se;
    }
}
void Dfs(int u, map<int, pii>& mp) { // mp[a_i] = min_i, cnt
    if (g[u].empty()) {
        mp[a[u]] = {inf, 1};
        ans[u] = 1ll * inf * inf;
        return;
    }
    Dfs(son[u], mp);
    ans[u] = ans[son[u]];
    add(u, a[u], 1, mp);
    for (auto v : g[u]) {
        if (v == son[u]) continue;
        map<int, pii> tem;
        Dfs(v, tem);
        for (auto it : tem)
            add(u, it.ft, it.se.se, mp);
    }
}

void work() {
    cin >> n;
    for (int i = 2; i <= n; i++) {
        cin >> fa[i];
        g[fa[i]].emplace_back(i);
    }
    cinarr(a, n);
    dfs(1);
    map<int, pii> tem;
    Dfs(1, tem);
    for (int i = 1; i <= n; i++) cout << (ans[i] != 1ll * inf * inf ? ans[i] : 0) << endl;
}

signed main() {
#ifdef LOCAL
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.in", "r", stdin);
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int Case = 1;
    //cin >> Case;
    while (Case--) work();
    return 0;
}
/*
     _____   _   _       _  __    __
    |  _  \ | | | |     | | \ \  / /
    | |_| | | | | |     | |  \ \/ /
    |  ___/ | | | |  _  | |   }  {
    | |     | |_| | | |_| |  / /\ \
    |_|     \_____/ \_____/ /_/  \_\
*/

关于代码的亿点点说明：

代码的主体部分位于 void work() 函数中，另外会有部分变量申明、结构体定义、函数定义在上方。

#pragma ... 是用来开启 O2、O3 等优化加快代码速度。

中间一大堆 #define ... 是我习惯上的一些宏定义，用来加快代码编写的速度。

"debug.h" 头文件是我用于调试输出的代码，没有这个头文件也可以正常运行（前提是没定义 DEBUG 宏），在程序中如果看到 dbg(...) 是我中途调试的输出的语句，可能没删干净，但是没有提交上去没有任何影响。

ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 这三句话是用于解除流同步，加快输入 cin 输出 cout 速度（这个输入输出流的速度很慢）。在小数据量无所谓，但是在比较大的读入时建议加这句话，避免读入输出超时。如果记不下来可以换用 scanf 和 printf，但使用了这句话后，cin 和 scanf、cout 和 printf 不能混用。

将 main 函数和 work 函数分开写纯属个人习惯，主要是为了多组数据。