仓鼠找sugar II
题目描述
小仓鼠的和他的基（mei）友（zi）sugar住在地下洞穴中，每个节点的编号为1~n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室（a，是任意的）他的基友卧室（b，还是任意的）。（注意，a有可能等于b。）然而小仓鼠学OI学傻了，不知道怎么怎么样才能最短的走到目的地。于是他只能随便乱走。当他在每一个节点时，等概率到这个点的母亲或者所有孩子节点（例如这个节点有一个母亲节点和两个子节点，那么下一步走到这3个节点的概率都是1/3）。一但走到了他基友的卧室，就会停下。
现在小仓鼠希望知道，他走到目的地时，走的步数的期望。这个期望本来是一个有理数，但是为了避免误差，我们要求对这个有理数取模，%998244353。
下面是“分数”模运算的定义：
b, m互质
k = a/b (mod m) <=> kb = a (mod m)
这里求 x = 1/17 (mod 2668)
<=>
17x = 1 (mod 2668)
<=>
17x = 2668k + 1 （k∈整数）
取合适的k使得17|(2668k+1) 这里刚好17 | (2668 + 1)
所以k = 1, x = (2668+1)/17 = 157
当然，当k = 1 + 17n 时，
x = (2668 + 17·n·2668 + 1)/17 = 157 + 2668n
也符合条件（n任意整数）
但如果限定 2668 > x > 0，x是唯一的。
小仓鼠那么弱，还要天天被JOHNKRAM大爷虐，请你快来救救他吧！
输入输出格式
输入格式：
第一行一个正整数n，表示这棵树节点的个数。
接下来n-1行，每行两个正整数u和v，表示节点u到节点v之间有一条边。
输出格式：
一个整数，表示取模后的答案。
输入输出样例
输入样例#1：
3
1 2
1 3
输出样例#1：
110916041
说明
对于30%的数据 n<=5；
对于50%的数据 n<=5000；
对于所有数据 n<=100000。
样例解释
期望是16/9
如果a在叶子 b在根，E1=1。有2种情况。
如果a在根，b在叶子。E2=1/2+3*1/4+5*1/8…=3。有2种情况。
【仓鼠找sugar II】如果a和b都在不同的叶子，E3=E2+1。有2种情况。
如果a=b，E4=0，有3种情况。
所以期望是16/9，有理数取模后就是输出。
设f[u->v]表示u、v之间有边的情况下，从u到v的期望距离。考虑从u出发第一步走到哪里可以列出方程f[u->v]=1/d[u]+sum{(1+f[k->u]+f[u->v])/d[u]}(u、k之间有边且k!=v)，d[u]表示u的度数。解方程得f[u->v]=d[u]+sum{f[k->u]}(u、k之间有边且k!=v)。把f[k->u]一层层代入，可得f[u->v]=sum{d[i]}(i在以v为根时u的子树内)。考虑每条边被计算了多少次，化简得f[u->v]=2siz[v][u]-1，siz[v][u]表示以v为根时u的子树大小。只需要计算出所有的siz[1][i]，那么判断一下u和v谁是父亲就可以O(1)的计算出siz[v][u]，进而计算出f[u->v]。
接下来考虑如何计算答案。因为期望的线性性，路径长度的期望等于每条边长度期望的和，所以考虑每条边在多少条路径中出现过，即可得出一条有向边u->v对答案的贡献是siz[v][u]*siz[u][v]*f[u->v]/n/n。对每条边各计算一次即可，时间复杂度O(n)。
const p=998244353;
var
tot,i,u,v:longint;
n:int64;
head,ret,next,size,w,ans,f,g:array[0..200022] of int64;
procedure ins(u,v:longint);
begin
tot:=tot+1;
ret[tot]:=v;
next[tot]:=head[u];
head[u]:=tot;
end;
function gpow(x,k:int64):int64;
var
t:int64;
begin
t:=1;
while k>0 do
begin
if k and 1=1 then t:=t*x mod p;
x:=x*x mod p;
k:=k >> 1;
end;
exit(t);
end;
procedure dfs(u,pre:longint);
var
i,v:longint;
begin
i:=head[u];
size[u]:=1;
while i<>0 do
begin
v:=ret[i];
if v<>pre then
begin
dfs(v,u);
w[i xor 1]:=2*size[v]-1;
w[i]:=2*n-2-w[i xor 1];
size[u]:=size[u]+size[v];
end;
i:=next[i];
end;
i:=head[u];
while i<>0 do
begin
v:=ret[i];
if v<>pre then
begin
f[u]:=(f[u]+f[v]+(size[v])*w[i xor 1]) mod p;
g[u]:=(g[u]+g[v]+(size[v])*w[i]) mod p;
ans[u]:=(ans[u]+g[v]*(size[u]-size[v]) mod p+(size[v])*(size[u]-size[v])*w[i] mod p+(size[v])*(size[u]-size[v])*w[i xor 1] mod p+f[v]*(size[u]-size[v]) mod p+ans[v]) mod p;
end;
i:=next[i];
end;
end;
begin
tot:=1;
readln(n);
for i:=1 to n-1 do
begin
readln(u,v);
ins(u,v);
ins(v,u);
end;
dfs(1,-1);
write(gpow(n*n mod p,p-2)*ans[1] mod p);
end.
推荐阅读
- 如何寻找情感问答App的分析切入点
- 2021-02-10（找不回的“年味”……）
- 好想，找个大海去裸奔…
- 拿着旧地图，找不到新大陆
- 三国谋略22（找准你的定位）
- 霍兰德职业代码对照表
- 寻找春天（2018.3）
- 寻找天使啦~~~
- 口红选得好，对象不愁找......
- 繁华声遁入空门