2020-team9/XXXXX

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr LL mod = 998244353;
constexpr int maxn = 50000 + 1;
constexpr int maxm = 200;
int n, m;
LL dp[maxn][2][maxm];
LL tmp[maxm];
vector<int> G[maxn];
int sz[maxn], hk[maxn];
void add(LL& x, LL y){
    x += y;
    if(x >= mod) x -= mod;
}
void DFS(int u, int p = 0){
    sz[u] = 1;
    for(int v : G[u]) if(v != p){
        DFS(v, u);
        sz[u] += sz[v];
        if(sz[v] > sz[hk[u]]) hk[u] = v;
    }
    if(hk[u] == 0){
        dp[u][0][0] = 1;
        return;
    }
    for(int i = 0; i < m; i += 1){
        dp[u][0][i] = (dp[hk[u]][0][i] + 2 * dp[hk[u]][1][i]) % mod;
        dp[u][1][i] = (2 * dp[hk[u]][0][i] + 2 * dp[hk[u]][1][i]) % mod;
    }
    for(int v : G[u]) if(v != p and v != hk[u]){
        for(int i = 0; i < m; i += 1) tmp[i] = 0;
        for(int i = 0; i < m; i += 1){
            LL k = (dp[v][0][i] + 2 * dp[v][1][i]) % mod;
            if(k) for(int j = 0; j < m; j += 1)
                add(tmp[(i + j) % mod], k * dp[u][0][j] % mod);
        }
        for(int i = 0; i < m; i += 1) dp[u][0][i] = tmp[i];

        for(int i = 0; i < m; i += 1) tmp[i] = 0;
        for(int i = 0; i < m; i += 1){
            LL k = (2 * dp[v][0][i] + 2 * dp[v][1][i]) % mod;
            if(k) for(int j = 0; j < m; j += 1)
                add(tmp[(i + j) % mod], k * dp[u][1][j] % mod);
        }
        for(int i = 0; i < m; i += 1) dp[u][1][i] = tmp[i];
    }
    for(int i = 0; i < m; i += 1) tmp[i] = (dp[u][1][i] - dp[u][0][i] + mod) % mod;
    for(int i = 0; i < m; i += 1) dp[u][1][i] = tmp[(i + m - 1) % m];

    if(0)for(int i = 0; i < m; i += 1){
        cout << u << " " << 0 << " " << i << " " << dp[u][0][i] << "\n";
        cout << u << " " << 1 << " " << i << " " << dp[u][1][i] << "\n";
    }
}
int main(){
    ios::sync_with_stdio(false);
    n = 50000, m = 200; 
    cin >> n >> m;
    for(int i = 1, u, v; i < n; i += 1){
        u = i; v = i + 1;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    DFS(1);
    cout << (dp[1][0][0] + dp[1][1][0]) % mod;
    return 0;
}

#include

using namespace std;

using LL = long long;

constexpr LL mod = 998244353;

constexpr int maxn = 50000 + 1;

constexpr int maxm = 200;

int n, m;

LL dp[maxn][2][maxm];

LL tmp[maxm];

vector G[maxn];

int sz[maxn], hk[maxn];

void add(LL& x, LL y){

x += y;

if(x >= mod) x -= mod;

}

void DFS(int u, int p = 0){

sz[u] = 1;

for(int v : G[u]) if(v != p){

DFS(v, u);

sz[u] += sz[v];

if(sz[v] > sz[hk[u]]) hk[u] = v;

}

if(hk[u] == 0){

dp[u][0][0] = 1;

return;

}

for(int i = 0; i < m; i += 1){

dp[u][0][i] = (dp[hk[u]][0][i] + 2 * dp[hk[u]][1][i]) % mod;

dp[u][1][i] = (2 * dp[hk[u]][0][i] + 2 * dp[hk[u]][1][i]) % mod;

}

for(int v : G[u]) if(v != p and v != hk[u]){

for(int i = 0; i < m; i += 1) tmp[i] = 0;

for(int i = 0; i < m; i += 1){

LL k = (dp[v][0][i] + 2 * dp[v][1][i]) % mod;

if(k) for(int j = 0; j < m; j += 1)

add(tmp[(i + j) % mod], k * dp[u][0][j] % mod);

}

for(int i = 0; i < m; i += 1) dp[u][0][i] = tmp[i];

for(int i = 0; i < m; i += 1) tmp[i] = 0;

for(int i = 0; i < m; i += 1){

LL k = (2 * dp[v][0][i] + 2 * dp[v][1][i]) % mod;

if(k) for(int j = 0; j < m; j += 1)

add(tmp[(i + j) % mod], k * dp[u][1][j] % mod);

}

for(int i = 0; i < m; i += 1) dp[u][1][i] = tmp[i];

}

for(int i = 0; i < m; i += 1) tmp[i] = (dp[u][1][i] - dp[u][0][i] + mod) % mod;

for(int i = 0; i < m; i += 1) dp[u][1][i] = tmp[(i + m - 1) % m];

if(0)for(int i = 0; i < m; i += 1){

cout << u << " " << 0 << " " << i << " " << dp[u][0][i] << "\n";

cout << u << " " << 1 << " " << i << " " << dp[u][1][i] << "\n";

}

}

int main(){

ios::sync_with_stdio(false);

n = 50000, m = 200;

cin >> n >> m;

for(int i = 1, u, v; i < n; i += 1){

u = i; v = i + 1;

cin >> u >> v;

G[u].push_back(v);

G[v].push_back(u);

}

DFS(1);

cout << (dp[1][0][0] + dp[1][1][0]) % mod;

return 0;

}