题解归档 - cf915F

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf915F
• 本地来源：problems/cf915F/idea.md
• 题目链接：https://codeforces.com/contest/915/problem/F
• 原始标题：CF915F — Imbalance Value of a Tree

思路

CF915F — Imbalance Value of a Tree

题意

给定一棵 n 点的树，点 i 权值为 a_i。对无序点对 (x,y)（x≠y），定义路径上的 不平衡值：

[
I(x,y) = \max_{v\in path(x,y)} a_v - \min_{v\in path(x,y)} a_v
]

求所有无序点对的 I(x,y) 之和。

关键转化

[
\sum_{x<y} I(x,y) = \sum_{x<y}(\max - \min)
]

按权值 v 贡献计数：若点对 (x,y) 的路径上 最小值 ≤ v ≤ 最大值，则 v 对该点对的 I 贡献为 1（最终差值可看作每个满足条件的 v 各 +1）。

因此对每个 v，只需统计满足 min(path) ≤ v ≤ max(path) 的无序点对个数。

算法（值域桶 + 两次 DSU）

记 tot = n(n-1)/2。

第一次（值从大到小激活点）
按 a_i 降序把点加入 DSU，合并时 le += sz_u * sz_v 统计 已连通的无序点对数。
处理完所有 a_i ≥ v 的点后，令 gep[v] = le，表示 路径最小值 ≥ v 的点对数量（路径上所有点权都 ≥ v 等价于 min ≥ v）。

第二次（值从小到大激活点）
同样 DSU，此时 le 表示 只含已激活（权值 ≤ 当前 v-1）点 的连通块内无序点对数，即 路径最大值 ≤ v-1 的点对数。

对每个权值 v，在把 a_i = v 的点加入 DSU 之前：

[
\text{contrib}(v) = tot - gep[v] - le
]

• gep[v]：min ≥ v → min > v-1，即 max 不可能 ≤ v-1 的那部分里 min 仍 ≥ v 的对数
• le：max ≤ v-1 的对数
• 剩余即为 min ≤ v ≤ max 的对数

累加 v * contrib(v) 即得答案（此处 contrib 是「v 出现在 [min,max] 区间内」的对数，等价于对每个 v 加一次计数；实现里直接 ans += tot - le - gep[i] 再 addv，因为每个 v 贡献 1 次计数，最后等价于按 v 加权）。

实现细节：同权值点按桶 bk[i] 批量 addv；并查集路径压缩 + 按大小合并；O(n α(n))，值域 ≤ 10^6 用 vector 桶。

样例

树：中心 1 连 2,3,4；权值 [2,2,3,1]。
6 个无序点对的不平衡值之和 = 6。

复杂度

• 时间：O(n α(n) + n + V)，V = max(a_i)
• 空间：O(n + V)

对拍

brute.cpp：枚举 i≤j，BFS 求路径 max/min；gen.cpp 随机树 n≤45。

链接

https://codeforces.com/contest/915/problem/F

代码

来源：problems/cf915F/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:36:43
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=1000005;
ll n,i,j,k,zc,pd,cur,dq,cnt,ans,tot,le,ge,mx;
ll a[maxn+5],fa[maxn+5],sz[maxn+5],on[maxn+5];
vector<ll>ss[maxn+5],gep;
vector<vector<ll>>bk;
ll findf(ll x){
    if(fa[x]!=x) fa[x]=findf(fa[x]);
    return fa[x];
}
void addv(ll x){
    on[x]=1,sz[x]=1;
    for(zc=0;zc<(ll)ss[x].size();zc++){
        pd=ss[x][zc];
        if(!on[pd]) continue;
        cur=findf(x),dq=findf(pd);
        if(cur!=dq){
            le+=sz[cur]*sz[dq];
            fa[cur]=dq,sz[dq]+=sz[cur];
        }
    }
}
int main(){
    ll x,y;
    cin>>n;
    mx=0;
    for(i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]>mx) mx=a[i];
    }
    bk.assign(mx+1,vector<ll>()),gep.assign(mx+1,0);
    for(i=1;i<=n;i++) bk[a[i]].push_back(i);
    for(i=1;i<n;i++){
        cin>>x>>y;
        ss[x].push_back(y),ss[y].push_back(x);
    }
    tot=n*(n-1)/2;
    le=0;
    for(i=1;i<=n;i++) on[i]=0,fa[i]=i,sz[i]=1;
    for(i=mx;i>=1;i--){
        for(j=0;j<(ll)bk[i].size();j++) addv(bk[i][j]);
        gep[i]=le;
    }
    le=0;
    for(i=1;i<=n;i++) on[i]=0,fa[i]=i,sz[i]=1;
    ans=0;
    for(i=1;i<=mx;i++){
        ans+=tot-le-gep[i];
        for(j=0;j<(ll)bk[i].size();j++) addv(bk[i][j]);
    }
    cout<<ans<<endl;
    return 0;
}