LOJ #2473. 「九省联考 2018」秘密袭击

时间：2022-10-03 03:34:25

#2473. 「九省联考 2018」秘密袭击

链接

分析：

　　首先枚举一个权值W，计算这个多少个连通块中，第k大的数是这个权值。

　　$f[i][j]$表示到第i个节点，有j个大于W数的连通块的个数。然后背包转移。

　　复杂度是$O(n^2k)$，时限5s，然后卡卡常就过了。

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef unsigned int ui;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = , mod = ;

struct Edge{ int to, nxt; } e[N << ];

int head[N], id[N], fa[N], st[N], ed[N], a[N];

ui f[N][N];

int n, k, w, Now, En;

inline bool cmp(int x,int y) { return a[x] == a[y] ? x <= y : a[x] < a[y]; }

inline void add_edge(int u,int v) {

    ++En; e[En].to = v, e[En].nxt = head[u]; head[u] = En;

    ++En; e[En].to = u, e[En].nxt = head[v]; head[v] = En;

}

void dfs(int u) {

    for (int i = st[u]; i <= ed[u]; ++i) f[u][i] = ;

    if (cmp(Now, u)) st[u] = ed[u] = ;

    else st[u] = ed[u] = ;

    f[u][st[u]] = ;

    for (int i = head[u]; i; i = e[i].nxt) {

        int v = e[i].to;

        if (v == fa[u]) continue;

        fa[v] = u;

        dfs(v);

        for (int j = ed[u]; j >= st[u]; --j)

            for (int k = ed[v]; k >= st[v]; --k)

                f[u][j + k] = (f[u][j + k] + f[u][j] * f[v][k]) % mod;

        ed[u] += ed[v];

    }

    for (int i = st[u]; i <= ed[u]; ++i) f[][i] = (f[][i] + f[u][i]) % mod;

}

int main() {

    n = read(), k = read(), w = read();

    for (int i = ; i <= n; ++i) a[i] = read();

    for (int i = ; i < n; ++i) {

        int u = read(), v = read();

        add_edge(u, v);

    }

    for (int i = ; i <= n; ++i) id[i] = i;

    sort(id + , id + n + , cmp);

    ui ans = ;

    for (int i = ; i <= n; ++i) {

        memset(f[], , sizeof(f[]));

        Now = id[i];

        dfs();

        for (int j = k; j <= n; ++j)

            ans = (ans + f[][j] * (a[id[i]] - a[id[i - ]])) % mod;

    }

    cout << ans % mod;

    return ;

}

相关文章