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

登录—专业IT笔试面试备考平台_牛客网


换根dp思想：维护两个变量f[i] 表示在包含这个点的子树中只包含这个点自身的连通块数，g[i]表示

在包含这个点的子树中所有联通块数量，显然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;
}

 前后缀积

#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;
}

最后

以上就是懦弱手机为你收集整理的一人行者（换根dp，前缀积，后缀积）的全部内容，希望文章能够帮你解决一人行者（换根dp，前缀积，后缀积）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。