链接：https://www.nowcoder.com/acm/contest/156/F

来源：牛客网

题目描述

题目背景编不下去了

托米有一棵有根树 T, 树根为1，每轮他会在剩下的子树中等概率一个点 u, 砍掉 u 的子树 (包含 u)，如果树上的点都被砍光了，游戏结束。

求出这个游戏进行的期望轮数，可以证明这个数一定是有理数，设他为 , 你需要告诉他一个整数 x 满足

输入描述:

第一行输入一个数 n， 表示 T 的点数，下面 n- 行给出了 T 的每条边

输出描述:

一行一个整数表示答案

示例1

输入

复制

输出

复制

备注:

n ≤ 

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

#define ll long long

vector<int>p[];

int deep[];

#define mod 998244353

void dfs(int x,int pre)

{

    for(int i=;i<p[x].size();i++)

    {

        if(p[x][i]==pre)

            continue;

        deep[p[x][i]]=deep[x]+;

        dfs(p[x][i],x);

    }

}

ll qsm(ll a,ll b,ll c)

{

    ll ans=;

    while(b)

    {

        if(b&)

            ans=ans*a%c;

        b=b/;

        a=a*a%c;

    }

    return ans;

}

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=;i<n;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        p[x].push_back(y);

        p[y].push_back(x);

    }

    deep[]=;

    dfs(,);

//    cout<<deep[1]<<" "<<deep[2]<<" "<<deep[3]<<endl;

    long long ans=;

    for(int i=;i<=n;i++)

    {

        ans=ans+qsm(deep[i],mod-,mod);

        ans=ans%mod;

    }

    cout<<ans<<endl;

    return ;

}