题目
题解
一脸min-max容斥的样子，设$f_{i,S}$表示起点为$i$，要求遍历的集合为
$S$，第一次遍历到集合中的点的期望最早时间，分情况讨论：
- 设现在遍历到的点为$x$，如果$x\in S$，那么$f_{x,S}$且$x$的子树不会产生贡献
- 如果$x \not \in S$，那么有转移$f_{x,S}=\frac{1}{du_x}(f_{fa_x,S}+1)+\frac{1}{du_x}\sum_{y\in son_x}(f_{y,S}+1)$
发现每个式子可以写成$f_{x,S}=A_x\times f_{fa_x,S}+B_x$的形式
代入得：$A_x=\frac{1}{du_x-\sum_{y\in son_x}A_y},B_x=\frac{du_x+\sum_{y\in son_x}B_y}{du_x-\sum_{y\in son_x}A_y}$
一遍$dfs$处理出$A,B$，然后用$FWT$优化处理子集卷积就行了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define _ for
# define __ int
# define ___ MAX
# define ____ char
# define _____ getchar
# define ______ struct
# define _______ return
# define ________ void
# define _________ 1ll
# define __________ using namespace std;
# define ___________ isdigit
# define ____________ printf
# define _____________ while
# define ______________ if
# define _______________ <<
# define ________________ const
# define _________________________________________________ ++
# define ___________________________________________________ "%d\n"
__________
________________ __ ___=1 _______________ 18,____________________________________=998244353;
______ ___________________________________________{
__ ____________________________,_____________________________________;
}____________________________________________[___ _______________ 1];
__ ______________________,__________________________________________,___________________________________,___________________________,_____________________;
__ ________________________[18],________________________________[18],_____________________________[___],_______________________________________________[18],_______________________________[18],D[18];
__ _________________________________________()
{
__ ____________________________(0);
____ ______________________________________________=_____();
_(;!___________(______________________________________________);______________________________________________=_____());
_(;___________(______________________________________________);____________________________=____________________________*10+______________________________________________-48,______________________________________________=_____());
_______ ____________________________;
}
________ ________________________________________(__ ____________________________,__ _____________________________________)
{
_________________________________________________ _______________________________[____________________________],____________________________________________[_________________________________________________ ___________________________]=(___________________________________________){_______________________________________________[____________________________],_____________________________________},_______________________________________________[____________________________]=___________________________;
_________________________________________________ _______________________________[_____________________________________],____________________________________________[_________________________________________________ ___________________________]=(___________________________________________){_______________________________________________[_____________________________________],____________________________},_______________________________________________[_____________________________________]=___________________________;
}
__ _____________________________________________(__ _____________________________,__ ______________________________)
{
__ ______________________________________=1;
_(;______________________________;______________________________>>=1,_____________________________=_________*_____________________________*_____________________________%____________________________________)
______________(______________________________&1) ______________________________________=_________*______________________________________*_____________________________%____________________________________;
_______ ______________________________________;
}
________ _________________(__ ____________________________,__ __________________________________________________,__ ___________________________________)
{
______________(___________________________________&(1 _______________ ____________________________)) _______ ________(________________________[____________________________]=________________________________[____________________________]=0);
__ _________________________________=0,__________________________________=0;
_(__ _______________________=_______________________________________________[____________________________],_____________________________________;_______________________;_______________________=____________________________________________[_______________________].____________________________)
______________((_____________________________________=____________________________________________[_______________________]._____________________________________)^__________________________________________________) _________________(_____________________________________,____________________________,___________________________________),(_________________________________+=________________________[_____________________________________])%=____________________________________,(__________________________________+=________________________________[_____________________________________])%=____________________________________;
________________________[____________________________]=_____________________________________________((_______________________________[____________________________]-_________________________________+____________________________________)%____________________________________,____________________________________-2),________________________________[____________________________]=_________*(_______________________________[____________________________]+__________________________________)%____________________________________*________________________[____________________________]%____________________________________;
}
__ __________________(__ ____________________________)
{
__ ___________________________=0;
_____________(____________________________) ____________________________&=____________________________-1,_________________________________________________ ___________________________;
_______ ___________________________;
}
________ ____________________(__ *________________________)
{
_(__ _______________________=1;_______________________<_____________________;_______________________=_______________________ _______________ 1)
_(__ ________________________________________________=_______________________ _______________ 1,_______________________________________=0;_______________________________________<_____________________;_______________________________________+=________________________________________________)
_(__ _________________________=0;_________________________<_______________________;_________________________________________________ _________________________)
(________________________[_______________________+_______________________________________+_________________________]+=________________________[_______________________________________+_________________________])%=____________________________________;
}
__ main()
{
______________________=_________________________________________(),_____________________=1 _______________ ______________________,__________________________________________=_________________________________________(),___________________________________=_________________________________________()-1;
_(__ _______________________=1;_______________________<______________________;_________________________________________________ _______________________)
________________________________________(_________________________________________()-1,_________________________________________()-1);
_(__ _______________________=0;_______________________<_____________________;_________________________________________________ _______________________)
_________________(___________________________________,-1,_______________________),_____________________________[_______________________]=(__________________(_______________________)&1?________________________________[___________________________________]:(____________________________________-________________________________[___________________________________])%____________________________________);
____________________(_____________________________);
_(__ _______________________=1,_________________________,__________________________;_______________________<=__________________________________________;_________________________________________________ _______________________)
{
_________________________=_________________________________________(),__________________________=0;
_(__ _______________________________________=1;_______________________________________<=_________________________;_________________________________________________ _______________________________________)
__________________________|=(1 _______________ _________________________________________()-1);
____________(___________________________________________________,_____________________________[__________________________]);
}
_______ 0;
}
