一人行者（换根dp，前缀积，后缀积）

110 阅读 0 评论 73 点赞

我是靠谱客的博主懦弱手机，这篇文章主要介绍一人行者（换根dp，前缀积，后缀积），现在分享给大家，希望可以做个参考。

在包含这个点的子树中所有联通块数量，显然f[u]=(f[v1]+1)*(f[v2]+1)*...*(f[vm]+1); g[u]为子树中所有节点f[v]值之和，对于一条边来说包含儿子节点v那一边的答案就是g[v] ,而包含父亲节点u的那一边显然需要算出以u为根时的f[u],然后再算出不包含子树v的f[u]，然后父亲那一边就是

g[1]-g[v]-f[u](旧的)+f[u]（换根更新过的）

然后数据大坑，f[v]+1==mod时，不能求逆元，所以全程( f[u] / (f[v]+1) )不能用逆元，需要用前缀后缀积的手段提前算出；

带逆元的错误写法

复制代码

#include<bits/stdc++.h>
#define endl 'n'
#define int long long
#define fi first
#define se second
#define pb push_back
#define lowbit(x) ((x)&(-x))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define all(x) x.begin(),x.end()
#define SZ(x) ((int)(x).size())
#define debug(var) cout<< #var << " = " << var << endl
using namespace std;
std::mt19937_64 rng;
const int N = 5e5 + 10, M = 4e5 + 10, mod = 998244353;
typedef pair<int, int>PII;
int m, n;
//

int qpow(int x, int n)
{
    int ans = 1;
    while(n)
    {
        if(n % 2) ans = ans * x % mod;
        x = x * x % mod;
        n /= 2;
    }
    return ans;
}

PII ans[N];
vector<PII >vs[N];

int g[N], f[N];

void dfs(int u, int fa)
{
    f[u] = 1;
    for(auto [v, id] : vs[u])
    {
        if(v == fa) continue;
        dfs(v, u);
        f[u] = f[u] * (f[v] + 1) % mod;
        g[u] += g[v];
        g[u] %= mod;
    }
    g[u] += f[u];
    g[u] %= mod;
}

void dfs2(int u, int fa)
{

for(auto [v, id] : vs[u])
    {
        if(v == fa) continue;

int t = (g[1] - g[v] - f[u] + 2 * mod) % mod + f[u] * qpow((f[v] + 1) % mod, mod - 2) % mod;

//   debug( f[u] * qpow((f[v] + 1) % mod, mod - 2) % mod);
        t %= mod;

ans[id / 2] = {t, g[v] % mod};

if(id % 2) ans[id / 2] = { g[v] % mod, t};

if(v == 8) debug(f[u] * qpow((f[v] + 1) % mod, mod - 2) % mod);

f[v] *= (1 + f[u] * qpow((f[v] + 1) % mod, mod - 2) % mod) % mod;

// debug(f[v]);
        cout << endl;
        g[v] %= mod, f[v] %= mod;

dfs2(v, u);
    }
}

void solve()
{
    cin >> n;
    int cnt = -1;
    rep(i, 0, n - 2)
    {
        int u, v;
        cin >> u >> v;
        vs[u].pb({v, ++cnt});
        vs[v].pb({u, ++cnt});
    }
    dfs(1, 0);
    rep(i, 1, n) cout << f[i] << " ";
    cout << endl;
    dfs2(1, 0);
    rep(i, 1, n) cout << f[i] << " ";
    cout << endl;
    // rep(i, 1, n)
    // {
    //     debug(f[i]), debug(g[i]);
    // }
    rep(i, 0, n - 2)
    {
        cout << ans[i].fi % mod << " " << ans[i].se % mod << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(12);
    int T = 1; //   cin>>T;
    while(T--)solve();
    return 0;
}

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<bits/stdc++.h>
#define endl 'n'
#define int long long
#define fi first
#define se second
#define pb push_back
#define lowbit(x) ((x)&(-x))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define all(x) x.begin(),x.end()
#define SZ(x) ((int)(x).size())
#define debug(var) cout<< #var << " = " << var << endl
using namespace std;
std::mt19937_64 rng;
const int N = 5e5 + 10, M = 4e5 + 10, mod = 998244353;
typedef pair<int, int>PII;
int m, n;
//


int qpow(int x, int n)
{
    int ans = 1;
    while(n)
    {
        if(n % 2) ans = ans * x % mod;
        x = x * x % mod;
        n /= 2;
    }
    return ans;
}

PII ans[N];
vector<PII >vs[N];

int g[N], f[N];

void dfs(int u, int fa)
{
    f[u] = 1;
    for(auto [v, id] : vs[u])
    {
        if(v == fa) continue;
        dfs(v, u);
        f[u] = f[u] * (f[v] + 1) % mod;
        g[u] += g[v];
        g[u] %= mod;
    }
    g[u] += f[u];
    g[u] %= mod;
}

void dfs2(int u, int fa)
{

    for(auto [v, id] : vs[u])
    {
        if(v == fa) continue;

        int t = (g[1] - g[v] - f[u] + 2 * mod) % mod + f[u] * qpow((f[v] + 1) % mod, mod - 2) % mod;

     //   debug( f[u] * qpow((f[v] + 1) % mod, mod - 2) % mod);
        t %= mod;

        ans[id / 2] = {t, g[v] % mod};

        if(id % 2) ans[id / 2] = { g[v] % mod, t};

        if(v == 8) debug(f[u] * qpow((f[v] + 1) % mod, mod - 2) % mod);

        f[v] *= (1 + f[u] * qpow((f[v] + 1) % mod, mod - 2) % mod) % mod;

        // debug(f[v]);
        cout << endl;
        g[v] %= mod, f[v] %= mod;

        dfs2(v, u);
    }
}


void solve()
{
    cin >> n;
    int cnt = -1;
    rep(i, 0, n - 2)
    {
        int u, v;
        cin >> u >> v;
        vs[u].pb({v, ++cnt});
        vs[v].pb({u, ++cnt});
    }
    dfs(1, 0);
    rep(i, 1, n) cout << f[i] << " ";
    cout << endl;
    dfs2(1, 0);
    rep(i, 1, n) cout << f[i] << " ";
    cout << endl;
    // rep(i, 1, n)
    // {
    //     debug(f[i]), debug(g[i]);
    // }
    rep(i, 0, n - 2)
    {
        cout << ans[i].fi % mod << " " << ans[i].se % mod << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(12);
    int T = 1; //   cin>>T;
    while(T--)solve();
    return 0;
}

前后缀积

复制代码

int qpow(int x, int n)
{
    int ans = 1;
    while(n)
    {
        if(n % 2) ans = ans * x % mod;
        x = x * x % mod;
        n /= 2;
    }
    return ans;
}

PII ans[N];
vector<PII >vs[N];
int g[N], f[N];

int pre[N], suf[N], val[N];

void dfs(int u, int fa)
{
    f[u] = 1;
    for(auto [v, id] : vs[u])
    {
        if(v == fa) continue;
        dfs(v, u);
        f[u] = f[u] * (f[v] + 1) % mod;
        g[u] += g[v];
        g[u] %= mod;
    }

suf[SZ(vs[u]) + 1] = pre[0] = 1;

// 前缀后缀积
    rep(i, 1, SZ(vs[u]))
    {
        auto [v, id] = vs[u][i - 1];
        if(v == fa) pre[i] = pre[i - 1];
        else pre[i] = pre[i - 1] * (f[v] + 1) % mod;
    }

per(i, SZ(vs[u]), 1)
    {
        auto [v, id] = vs[u][i - 1];
        if(v == fa) suf[i] = suf[i + 1];
        else  suf[i] = suf[i + 1] * (f[v] + 1) % mod;
      
    }

rep(i, 1, SZ(vs[u]))
    {

auto [v, id] = vs[u][i - 1];
        if(v==fa) continue;
        val[v] = pre[i - 1] * suf[i + 1] % mod;//  (只不包含v这个儿子的父亲的f[u]值)
    }

g[u] += f[u];
    g[u] %= mod;
}

void dfs2(int u, int fa, int k)
{
    rep(i, 0, SZ(vs[u]) - 1)
    {
        auto [v, id] = vs[u][i];

if(v == fa) continue;

val[v] = val[v] * k % mod;

int t = ((g[1] - g[v] - f[u] + 2 * mod) % mod + val[v])%mod;

if(id % 2) ans[id / 2] = { g[v] % mod, t};

else ans[id / 2] = {t, g[v] % mod};

f[v] = f[v]*(1+val[v]) % mod;

dfs2(v, u,  (1+val[v])%mod);// k参数的意思是专门更新前后缀积的
    }
}

void solve()
{
    cin >> n;
    int cnt = -1;
    rep(i, 0, n - 2)
    {
        int u, v;
        cin >> u >> v;
        vs[u].pb({v, ++cnt});
        vs[v].pb({u, ++cnt});
    }

dfs(1, 0);
    dfs2(1, 0, 1);

rep(i, 0, n - 2)
    {
        cout << ans[i].fi % mod << " " << ans[i].se % mod << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(12);
    int T = 1; //   cin>>T;
    while(T--)solve();
    return 0;
}

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<bits/stdc++.h>
#define endl 'n'
#define int long long
#define fi first
#define se second
#define pb push_back
#define lowbit(x) ((x)&(-x))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define all(x) x.begin(),x.end()
#define SZ(x) ((int)(x).size())
#define debug(var) cout<< #var << " = " << var << endl
using namespace std;
std::mt19937_64 rng;
const int N = 5e5 + 10, M = 4e5 + 10, mod = 998244353;
typedef pair<int, int>PII;
int m, n;
//


int qpow(int x, int n)
{
    int ans = 1;
    while(n)
    {
        if(n % 2) ans = ans * x % mod;
        x = x * x % mod;
        n /= 2;
    }
    return ans;
}

PII ans[N];
vector<PII >vs[N];
int g[N], f[N];


int pre[N], suf[N], val[N];

void dfs(int u, int fa)
{
    f[u] = 1;
    for(auto [v, id] : vs[u])
    {
        if(v == fa) continue;
        dfs(v, u);
        f[u] = f[u] * (f[v] + 1) % mod;
        g[u] += g[v];
        g[u] %= mod;
    }

    suf[SZ(vs[u]) + 1] = pre[0] = 1;


    // 前缀后缀积
    rep(i, 1, SZ(vs[u]))
    {
        auto [v, id] = vs[u][i - 1];
        if(v == fa) pre[i] = pre[i - 1];
        else pre[i] = pre[i - 1] * (f[v] + 1) % mod;
    }

    per(i, SZ(vs[u]), 1)
    {
        auto [v, id] = vs[u][i - 1];
        if(v == fa) suf[i] = suf[i + 1];
        else  suf[i] = suf[i + 1] * (f[v] + 1) % mod;
      
    }

    rep(i, 1, SZ(vs[u]))
    {

        auto [v, id] = vs[u][i - 1];
        if(v==fa) continue;
        val[v] = pre[i - 1] * suf[i + 1] % mod;//  (只不包含v这个儿子的父亲的f[u]值)
    }

    g[u] += f[u];
    g[u] %= mod;
}


void dfs2(int u, int fa, int k)
{
    rep(i, 0, SZ(vs[u]) - 1)
    {
        auto [v, id] = vs[u][i];

        if(v == fa) continue;

        val[v] = val[v] * k % mod;

        int t = ((g[1] - g[v] - f[u] + 2 * mod) % mod + val[v])%mod;

        if(id % 2) ans[id / 2] = { g[v] % mod, t};

        else ans[id / 2] = {t, g[v] % mod};

        f[v] = f[v]*(1+val[v]) % mod;

        dfs2(v, u,  (1+val[v])%mod);// k参数的意思是专门更新前后缀积的
    }
}


void solve()
{
    cin >> n;
    int cnt = -1;
    rep(i, 0, n - 2)
    {
        int u, v;
        cin >> u >> v;
        vs[u].pb({v, ++cnt});
        vs[v].pb({u, ++cnt});
    }

    dfs(1, 0);
    dfs2(1, 0, 1);

    rep(i, 0, n - 2)
    {
        cout << ans[i].fi % mod << " " << ans[i].se % mod << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(12);
    int T = 1; //   cin>>T;
    while(T--)solve();
    return 0;
}