社论：P16355 「Diligent-OI R3 C」彼方へ、名もなき海辺より

Jordan_Pan · 2026-04-26 20:03:15 · 题解

0

剩余十分钟拿到 50pts，最幽默。

1

题目定义了两张图不同的判定，显然这等价于任意一个点连的任意一条边不同。

记 b_u 为 u 的儿子个数，d_u 为 u 的祖先个数（不包括 u），那么 u 就能连 b_u+d_u 条边，记 c_u=b_u+d_u，总方案数为 \prod c_u，记为 m。

以每个连通块最浅的点为关键点计数。即枚举 u，统计 u 连通块内最浅的点为 u 的局面数量。其中 u=1 的数量就是 m。

现在需要把 u 和 fa_u 这条边断开，即强制 u 与 fa_u 不连通。

• 对于 u 子树外的其它点：fa_u 不能连向 u，只有 c_{fa_u}-1 种方法，而其它点没有限制。
• 对于 u：只能连向儿子，记这个儿子为 v。
  • 对于 u 除了 v 之外的其它子树：经过手玩可以发现，无论怎么连都无法将 u 和 fa_u 所在的连通块连起来，对“u 与 fa_u 不连通”的限制没有影响，所以它们可以随便连。
  • 对于 v：它可以连到 u 到 fa_v 这条链上，共 d_v-d_u 种方案，v 子树内的点可以随便连；也可以继续连向儿子，重复上述过程；但是不能连到 1 到 fa_u 这条链上，否则就破坏了“u 与 fa_u 不连通”的限制。

于是可以写出 O(n^2) 做法：枚举 u，枚举 u 向下连到的最深点 v（也就是基环树森林中环的最深点）。记 u\to v 为 u 到 v 的路径，那么除了这条路径上的点，其余点都无限制，这一对 (u,v) 对答案的贡献为 \frac{m}{\prod_{p\in(u\to v)}c_p}\times(d_v-d_u)。

简单优化即可做到 O(n)：树形 dp 分别维护 f_u=\sum_{v\in subtree_u}\frac{m}{\prod_{p\in u\to v}c_p} 以及 g_u=\sum_{v\in subtree_u}\frac{m\times d_v}{\prod_{p\in u\to v}c_p}，点 u 对答案的贡献即为 g_u-f_u\times d_u。

2

:::info[代码]

#include<bits/stdc++.h>
constexpr int rSiz=1<<21;
char rBuf[rSiz],*p1=rBuf,*p2=rBuf;
#define gc() (p1==p2&&(p2=(p1=rBuf)+fread(rBuf,1,rSiz,stdin),p1==p2)?EOF:*p1++)
template<class T>void rd(T&x){
    char ch=gc();
    for(;ch<'0'||ch>'9';ch=gc());
    for(x=0;ch>='0'&&ch<='9';ch=gc())
        x=(x<<1)+(x<<3)+(ch^48);
}
constexpr int _=5e5+5,mod=998244353;
void Add(int &x,int y){if((x+=y)>=mod)x-=mod;}
void Dec(int &x,int y){if((x-=y)<0)x+=mod;}
int pw(int x,int y=mod-2){
    for(int v=1;;y>>=1,x=1ll*x*x%mod){
        if(!y)return v;
        if(y&1)v=1ll*v*x%mod;
    }
}
int n,m,a[_],b[_],c[_],d[_],pc[_],f[_],g[_],h[_],ans;
std::basic_string<int>e[_];
void dfs1(int u,int fa){
    d[u]=d[fa]+1;f[u]=1;
    for(int v:e[u])if(v^fa){
        dfs1(v,u);++b[u];
        f[u]=1ll*f[u]*f[v]%mod;
    }
    c[u]=b[u]+d[u];pc[u]=pw(c[u]);
    f[u]=1ll*f[u]*c[u]%mod;
}
void dfs2(int u,int fa){
    for(int v:e[u])if(v^fa){
        dfs2(v,u);
        Add(g[u],g[v]);
        Add(h[u],h[v]);
    }
    if(!fa)return;
    Add(g[u],f[1]);
    g[u]=1ll*g[u]*pc[u]%mod;
    Add(h[u],1ll*f[1]*d[u]%mod);
    h[u]=1ll*h[u]*pc[u]%mod;
    int val=h[u];
    Dec(val,1ll*g[u]*d[u]%mod);
    val=1ll*val*pc[fa]%mod*(c[fa]-1)%mod;
    Add(ans,val);
    // printf("%d %d %d %d %d %d\n",u,c[u],f[u],g[u],h[u],val);
}
int main(){
    rd(n);d[0]=-1;
    for(int i=1,u,v;i<n;++i)rd(u),rd(v),e[u]+=v,e[v]+=u;
    dfs1(1,0);dfs2(1,0);
    Add(ans,f[1]);
    printf("%d\n",ans);
}

:::