QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#622030	#7895. Graph Partitioning 2	Doubeecat	TL	3ms	13444kb	C++23	2.4kb	2024-10-08 19:34:07	2024-10-08 19:34:07

Judging History

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

[2024-10-08 19:34:07]
评测

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

查看

[2024-10-08 19:34:07]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair <int,int>
const int N = 1e5 + 10;
const int K = 320;
const ll mod = 998244353;
unordered_map <int,int> DP[N],ttmp;
ll dp[N][K],n,k,tmp[N],siz[N];
vector <int> G[N];

void dfs1(int x,int fa) {
    dp[x][1] = 1;
    siz[x] = 1;
    for (auto y : G[x]) {
        if (y == fa) continue;
        dfs1(y,x);
        for (int i = 0;i <= k+1;++i) tmp[i] = 0;
        for (int j = 0;j <= min(siz[y],k);++j) {//这一步的上界为k，因为i要占用1个点
            for (int i = min(k+1 - j,siz[x]);i >= 1;--i) {
                tmp[i+j] = (tmp[i+j] + dp[x][i] * dp[y][j] % mod) % mod;
            }
        }
        siz[x] += siz[y];
        for (int i = 0;i <= k+1;++i) dp[x][i] = tmp[i];
    }
    dp[x][0] = (dp[x][k] + dp[x][k+1]) % mod;
    /*cout << "nowpoi:" << x << "\n";
    for (int i = 0;i <= k+1;++i) {
        cout << dp[x][i] << " ";
    }
    cout <<"\n";*/
}

void dfs2(int x,int fa) {
    DP[x][1] = 1;
    siz[x] = 1;
    for (auto y : G[x]) {
        if (y == fa) continue;
        dfs2(y,x);
        ttmp.clear();
        for (auto [j,val2] : DP[y]) {
            for (auto [i,val1] : DP[x]) {
                if (i + j > k+1) continue;
                ttmp[i+j] = (ttmp[i+j] + val1 * val2 % mod) % mod;
            }
        }
        DP[x].clear();
        for (auto [i,val1] : ttmp) DP[x][i] = val1;
        siz[x] += siz[y];
    }
    ll now = 0;
    if (DP[x].count(k)) now += DP[x][k];
    if (DP[x].count(k+1)) now += DP[x][k+1];
    DP[x][0] = (now % mod + mod )% mod;
    /*cout << "nowpoi:" << x <<"\n";
    for (auto [i,j] : DP[x]) {
        cout << i << " " << j << "\n";
    }
    cout <<"\n";*/

}

void solve() {
    cin >> n >> k;
    for (int i = 1;i <= n;++i) G[i].clear();
    for (int i = 1;i < n;++i) {
        int x,y;cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    int lim = sqrt(n);
    if (k <= lim) {
        for (int i = 1;i <= n;++i) {
            for (int j = 0;j <= k;++j) {
                dp[i][j] = 0;
            }
        }
        dfs1(1,0);
        cout << dp[1][0] << "\n";
    } else {
        DP[1].clear();
        dfs2(1,0);
        cout << DP[1][0] << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    int T;cin >> T;
    while (T--) solve();
    return 0;
}
/*
2
4 3
1 2
1 3
2 4
4 3
1 2
1 3
2 4
*/

源文件, 语言: C++23

詳細信息

Test #1:

score: 100

Accepted

time: 3ms

memory: 13444kb

input:

output:

2
1

result:

ok 2 lines

Test #2:

score: -100

Time Limit Exceeded

input:

output: