JZOJ-senior-5954. 【NOIP2018模拟11.5A组】走向巅峰

Time Limits: 1000 ms Memory Limits: 131072 KB Detailed Limits

Description

众所周知，DH是一位人生赢家，他不仅能虐暴全场，而且还正在走向人生巅峰；
在巅峰之路上，他碰到了这一题：
给出一棵n个节点的树，我们每次随机染黑一个叶子节点（可以重复染黑），操作无限次后，这棵树的所有叶子节点必然全部会被染成黑色。
定义R为这棵树不经过黑点的直径，求使R第一次变小期望的步数。

Input

第一行一个正整数n，表示树的点数。
接下来n−1行，每行两个正整数x,y，表示树上的一条边。

Output

输出一行一个整数表示答案在模 998244353意义下的取值。

Sample Input

输入1：
3
1 2
2 3

输入2：
6
1 2
2 3
1 4
4 5
1 6

Sample Output

输出1：
1

输出2：
499122178

Data Constraint

对于15%的数据，满足n<=10；
对于30%的数据，满足n<=1000；
另外有20%数据，满足树为菊花图；
另外有15%数据，满足每个点度数不超过3；
对于100%的数据，满足n<=5*10^5。

Solution

~~又是期望……万分绝望……~~
题目大意：给出一棵树，每次随机染黑一个叶子结点，最终全染黑，求直径第一次变小的期望步数
可以作为直径的组成部分的叶子结点可划分为一个个集合，当某一集合里全被染黑的时候，直径就变了

分情况讨论（这里我们将染黑称为删去）

1.直径为偶数
这种情况下一定能找到root，使得所有直径都经过它，以这个点为树根，给每个点定深度，记为 $dep_x$
显然，仅 $dep_x=R/2$ 的 $x$ 是可作为直径端点的点，其它的叶子结点均为无关点，统计出来 $m1$ 个
把所有的有用点按它属于root的哪个儿子划分成几个集合
直径改变，当且仅当只剩下一个集合里有没被删去的点

2.直径为奇数
显然有必经边，以这条边为分界线把树剖开，有用点形成两个集合，情况就和直径为偶数的一样了

可以推出，当全局还剩 $x$ 个叶子结点没被删去的时候，再删一个点的代价为 $\frac{m}{x}$ ， $m$ 为全部叶子数
对于无关点，我们视为一开始就删去了，也就是一开始就删了 $m1$ 个点

现在问题就转化为每次删一个没有删掉的点（带权），求删剩一个集合的期望
这个可以用（所有方案代价总和）/（方案数）的方法算概率

具体如下：
JZOJ-senior-5954. 【NOIP2018模拟11.5A组】走向巅峰

Code

#include<algorithm>
#include<cstdio>

#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define ll long long

using namespace std;

const int N=5e5+5,P=998244353;
int n,m,p1,p2,l1,l2,num,cnt,leaf;
int f[N],s[N],c[N],d[N],v[N],dep[N],last[N];
int jc[N],ny[N],ni[N];
struct edge{int to,next;}e[2*N];

void link(int x,int y)
{
	e[++num]=(edge){y,last[x]},last[x]=num;
}

void dfs1(int x,int fa,int dis)
{
	if(dis>l1) p1=x,l1=dis;
	for(int w=last[x];w;w=e[w].next)
		if(e[w].to!=fa) dfs1(e[w].to,x,dis+1);
}

void dfs2(int x,int fa,int dis)
{
	if(dis>l2) p2=x,l2=dis; f[x]=fa;
	for(int w=last[x];w;w=e[w].next)
		if(e[w].to!=fa) dfs2(e[w].to,x,dis+1);
}

void get(int x,int fa)
{
	if(dep[x]==(l2/2)) s[x]=1;
	int son=0;
	for(int w=last[x];w;w=e[w].next)
		if(!v[e[w].to])
		{
			++son;
			v[e[w].to]=1;
			dep[e[w].to]=dep[x]+1;
			get(e[w].to,x);
			s[x]+=s[e[w].to];
		}
	if(!son) ++m;
}

void divide_odd(int x,int y)
{
	v[x]=v[y]=1; get(x,0),get(y,0);
	d[++cnt]=s[x],d[++cnt]=s[y];
}

void divide_even(int x)
{
	v[x]=1; get(x,0);
	for(int w=last[x];w;w=e[w].next)
		if(s[e[w].to]) d[++cnt]=s[e[w].to];
}

void getmid()
{
	int x=p2,p=0;
	while(p<l2/2) ++p,x=f[x];
	if(l2&1) divide_odd(x,f[x]);
		else divide_even(x);
}

int ksm(int a,int b)
{
	int s=1;
	for(;b;a=(ll)a*(ll)a%P,b>>=1)
		if(b&1) s=(ll)s*(ll)a%P;
	return s;
}

void pre()
{
	fo(i,1,cnt) leaf+=d[i];
	jc[0]=1;
	fo(i,1,leaf) jc[i]=(ll)jc[i-1]*i%P;
	ny[leaf]=ksm(jc[leaf],P-2);
	fd(i,leaf-1,0) ny[i]=(ll)ny[i+1]*(ll)(i+1)%P;
	ni[0]=ni[1]=1;
	fo(i,2,leaf) ni[i]=P-(ll)(P/i)*(ll)ni[P%i]%P;
	fd(i,leaf,1) c[i]=((ll)c[i+1]+(ll)m*(ll)ni[i])%P;
}

int C(int n,int m)
{
	return (ll)jc[n]*(ll)ny[m]%P*(ll)ny[n-m]%P;
}

int solve()
{
	pre();
	int ans=0;
	fo(k,1,cnt)
		fo(i,0,d[k]-1)
		{
			int tmp=C(d[k],i);
			tmp=(ll)tmp*(ll)jc[leaf-d[k]+i-1]%P;
			tmp=(ll)tmp*(ll)(leaf-d[k])%P;
			tmp=(ll)tmp*(ll)c[d[k]-i+1]%P;
			tmp=(ll)tmp*(ll)jc[d[k]-i]%P;
			ans=((ll)ans+(ll)tmp)%P;
		}
	return (ll)ans*(ll)ny[leaf]%P;
}

int main()
{
	freopen("winer.in","r",stdin);
	freopen("winer.out","w",stdout);
	scanf("%d",&n);
	fo(i,1,n-1)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		link(x,y),link(y,x);
	}
	p1=l1=0,dfs1(1,0,0);
	p2=l2=0,dfs2(p1,0,0);
	getmid();
	printf("%d",solve());
}