WA on #4 求条
查看原帖
WA on #4 求条
549131
Eous楼主2024/12/3 19:02
#include<bits/extc++.h>
#define inv(x) binpow(x,mod - 2)
#define inf 0x7f7f7f7f7f7f
#define int long long
using namespace std;
const int mod = 998244353;
const int maxn = 2e5 + 5;
int n;  
int head[maxn],idx = 1;
int dep[maxn],son[maxn];
int k[maxn],dp[maxn];
struct edge
{
    int v,nxt;
    edge(int v = 0,int nxt = 0):v(v),nxt(nxt){};
}e[maxn << 1];
void adde(int u,int v)
{
    e[++ idx] = edge(v,head[u]);
    head[u] = idx;
}
int binpow(int x,int y)
{
    int ret = 1;
    while (y)
    {
        if (y & 1)
            ret = ret * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ret;
}
void init()
{
    for (int i = 2; i <= idx; i++)
        e[i] = edge();
    fill(head + 1,head + n + 1,0),idx = 1;
    fill(dep + 1,dep + n + 1,0);
    fill(son + 1,son + n + 1,0);
    fill(k + 1,k + n + 1,0);
    fill(dp + 1, dp + n + 1,0);
}
void dfs1(int u,int fa)
{
    dep[u] = dep[fa] + 1;
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].v;
        if (v == fa)
            continue;
        dfs1(v,u);
    }
}
void dfs2(int u,int fa)
{
    int _min = inf;
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].v;
        if (v == fa)
            continue;
        dfs2(v,u);
        if (_min > dep[v])
        {
            son[u] = son[v];
            _min = dep[son[v]];
            k[u] = inv((2 - k[v] + mod) % mod);
        }
    }
    if (_min == inf)
    {
        son[u] = u;
        k[u] = 0;
    }
}
void dfs3(int u,int fa)
{
    if (u == 1)
        dp[u] = 1;
    else
        dp[u] = dp[fa] * k[u] % mod;
    for (int i = head[u]; i; i = e[i].nxt)
        if (e[i].v != fa)
            dfs3(e[i].v,u);
}
void solve()
{
    init();
    scanf("%lld",&n);
    int x,y;
    for (int i = 1; i < n; i ++)
    {
        scanf("%lld%lld",&x,&y);
        adde(x,y);
        adde(y,x);
    }
    dfs1(1,0);
    dfs2(1,0);
    dfs3(1,0);
    for (int i = 1; i <= n; i++)
        printf("%lld ",dp[i]);
    putchar('\n');
}
signed main()
{
    int t;
    scanf("%lld",&t);
    while (t --)
        solve();
    return 0;
}
2024/12/3 19:02
加载中...