QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#624307	#7895. Graph Partitioning 2	afy	TL	3ms	24068kb	C++20	3.2kb	2024-10-09 15:30:23	2024-10-09 15:30:23

Judging History

你现在查看的是最新测评结果

[2024-10-09 15:30:23]
评测

测评结果：TL
用时：3ms
内存：24068kb

查看

[2024-10-09 15:30:23]
提交

answer

#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define deb(...)
#endif
using namespace std;
#define ll long long
// #define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define db double
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl "\n"
#define alls(x) (x).begin(), (x).end()
#define fs first
#define sec second
#define bug(x) cerr << #x << " = " << x << endl
const int N = 3e5 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int p = 998244353;
const double eps = 1e-8;
const double PI = acos(-1.0);
int T;
int n, K;
int f[N][666], siz[N], g[666];
unordered_map<int, int> F[N], G;
vector<int> e[N];
void chushihua() {
    for (int i = 1; i <= n; i++) e[i].clear();
    int sq = 660;
    if (K <= sq)
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= K + 1; j++) f[i][j] = 0;
    else
        F[1].clear();
}

void DFS1(int u, int fa) {
    // 当k<=sq时，直接记录包含当前子树根节点的连通块大小进行树上背包DP即可
    siz[u] = 1;
    f[u][1] = 1;
    for (auto v : e[u]) {
        if (v == fa)
            continue;
        DFS1(v, u);
        for (int j = 0; j <= K + 1; j++) g[j] = 0;  // 由于这个背包是必须强制选，所以之前的状态需要删除，我用临时数组g来实现转移。
        for (int j = 0; j <= min(K, siz[v]); j++) {
            for (int k = min(K + 1 - j, siz[u]); k >= 1; k--)
                (g[j + k] += (ll)((ll)f[v][j] * (ll)f[u][k]) % p) %= p;
        }
        for (int j = 0; j <= K + 1; j++) f[u][j] = g[j];
        siz[u] += siz[v];
    }
    f[u][0] = (f[u][K] + f[u][K + 1]) % p;
}

void DFS2(int u, int fa) {
    siz[u] = 1;
    F[u][1] = 1;  // k 比较大时
                  // 使用 unordered_map 记录答案不为 0 的值进行树上背包
    for (auto v : e[u]) {
        if (v == fa)
            continue;
        DFS2(v, u);
        G.clear();
        for (auto j : F[v]) {
            for (auto k : F[u]) {
                if (j.first + k.first > K + 1)
                    continue;
                (G[j.first + k.first] += (ll)((ll)j.second * (ll)k.second) % p) %= p;
            }
        }
        F[u].clear();
        for (auto j : G) F[u][j.first] = j.second;
        siz[u] += siz[v];
    }
    F[u][0] = (F[u][K] + F[u][K + 1]) % p;
}

void solve() {
    int x, y;
    chushihua();
    cin >> n >> K;
    deb(n, K);
    int sq = 660;
    for (int i = 1; i < n; i++) {
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    if (K <= sq) {
        DFS1(1, 1);
        cout << (f[1][0] % p + p) % p << endl;
    } else {
        DFS2(1, 1);
        cout << (F[1][0] % p + p) % p << endl;
    }
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
#ifdef LOCAL
    double starttime = clock();
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
#endif
    int t = 1;
    cin >> t;
    deb(t);
    while (t--) solve();
#ifdef LOCAL
    double endtime = clock();
    cerr << "Time Used: " << (double)(endtime - starttime) / CLOCKS_PER_SEC * 1000 << " ms" << endl;
#endif
    return 0;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 3ms

memory: 24068kb

input:

output:

2
1

result:

ok 2 lines

Test #2:

score: -100

Time Limit Exceeded

input:

output: