【UOJ 351】新年的叶子 / 题解

题目描述

对于一颗树,每次随机选择一个叶子,将其染黑,经过无数次操作以后,所有叶子将变成黑色。求期望在这之前的哪一时刻,不包含黑色点的直径长度第一次变小?

思路

首先我们找到这棵树的直径。如果直径长度是偶数,所有直径必有一个必经点,这个点为中点;如果直径长度是奇数,所有直径必有一条必经边,这条边也在直径的正中间。

我们沿着必经点或者必经边切开,能把树分成若干个集合,每个集合中有一些叶子是直径可能的端点。直径长度变小,当且仅当除剩下的一个集合外,所有集合中可能作为直径端点的叶子均被染黑。

于是我们可以枚举剩下哪个集合没有被全部染黑,分别计算贡献,最后容斥一下得出答案。

代码

#include 
#define maxn 500500
#define md 998244353
#define ll long long
using namespace std;
struct Edge{
    int to,next;
    Edge(int a=0,int b=0){
        to=a,next=b;
    }
}l[maxn<<1];
int head[maxn],f[maxn],q[maxn],t,leaf,cnt,tot,n,nod;
int pre[maxn],deg[maxn],inv[maxn],chain,ans,X,Y,S;
void Init(){
    inv[1]=1;
    for (register int i=2;i<=n;++i)
        inv[i]=(1ll*(md-md/i)*inv[md%i]%md+md)%md;
}
void Add(int a,int b){
    l[++cnt]=Edge(b,head[a]);
    head[a]=cnt;deg[b]++;
}
void Dfs(int u,int fa,int dis){
    if (dis>chain) chain=dis,nod=u;
    for (register int i=head[u];i;i=l[i].next){
        int v=l[i].to;
        if (v==fa) continue;
        pre[v]=u,Dfs(v,u,dis+1);
    }
}
void Sum(int u,int fa,int dis){
    if (dis==chain/2) tot++;
    for (register int i=head[u];i;i=l[i].next){
        int v=l[i].to;
        if (v==fa) continue;
        Sum(v,u,dis+1);
    }
}
int main(){
    scanf("%d",&n);Init();
    for (register int i=1,a,b;i
Show Comments