中位数相关

一般的中位数好像就只能sort了吧。。。还有01序列。

点

给定一棵 \(n\) 个点的树，每条边有一个 \([1,m]\) 中的边权（边权不确定）。

对于每个点 \(u\) 上都有一个数 \(a_{u}\)，要求 \(u\) 相连的所有边的边权的中位数不超过 \(a_{u}\)。问边权和的最大值。如果无解则输出 \(-1\)。（其实不存在无解）

中位数的定义：设共有 \(k\) 个数，将它们从小到大排序后第 \(\lfloor\frac{k}{2}\rfloor+1\) 个数即为中位数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>

using LL = long long;
using std::cin;
using std::cout;
using std::max;
using std::min;

const int maxn = 5e5+10;
//const LL inf = LLONG_MAX;

struct E{
    int v,pre;
}e[maxn*2];
int head[maxn],tot=1;
void add(int u,int v){
    e[++tot]={v,head[u]},head[u]=tot;
}
int n,m,a[maxn],deg[maxn];

LL f[maxn][2]; // 子树内边权和最大值
// f[u][0]--父亲边小于等于a_u
// f[u][1]--父亲边可以大于a_u

void dfs(int u,int fa){
    if(deg[u]==1 && fa!=0) {
        // 叶子
        f[u][0]=0; // 没有边。。。
        f[u][1]=LLONG_MIN;
        return ;
    }

    std::vector<LL> q;
    LL sum=0;
    for(int p=head[u];p;p=e[p].pre){
        int v=e[p].v;
        if(v==fa) continue;
        dfs(v,u);
        LL less = max(f[v][0]+min(a[u],a[v]), f[v][1]+a[u]); // w(u,v) 小于等于 a[u]
        LL more = max(f[v][0]+a[v], f[v][1]+m); // w(u,v) 可能大于 a[u]
        sum+=less;
        q.push_back(more-less);
    }
    f[u][0]=f[u][1]=sum;
    // 然后考虑补上尽可能多的差值 即最多选(deg[u]-1)/2个more替换掉less（加上差值）
    std::sort(q.begin(),q.end(),std::greater<LL>());
    for(int i=0;i<(deg[u]-1>>1)-1;i++){
        // 让f[u][1]少选一个
        if(q[i]>0) f[u][0]+=q[i], f[u][1]+=q[i];
    }

    if(deg[u]==2 && fa!=0) {
        // 链 俩边都得小于等于 a[u]
        f[u][1]=LLONG_MIN;
    }else {
        // f[u][0]多加一个
        if((deg[u]-1>>1)-1 >= 0) f[u][0]+=q[(deg[u]-1>>1)-1];
    }
}

int main(){
    std::ios::sync_with_stdio(0),cin.tie(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    for(int i=1,u,v;i<n;i++){
        cin >> u >> v;
        add(u,v),add(v,u);
        deg[u]++,deg[v]++;
    }

    dfs(1,0);
    cout << f[1][0];

    return 0;
}

01排序问题