牛客练习赛55E.树

题目链接
题解如下：

本人的做法比题解麻烦一点，也由于一个小地方的错误，导致博主调了很久。。。。。

其实也没什么好说的，细节题。
注意细节就行了，唯一的思维点就是转化问题，这个转化以前都没有接触过，是我太笨了。。

主要计算过程都写了注释
细节见代码：

#include<bits/stdc++.h>
typedef  long long LL;
#define fi first
#define se second
#define pb push_back
using namespace std;
const int N=1e6 + 11;
const LL mod=998244353;
int n;
vector<int>v[N];
LL f[N],siz[N];
LL ans=0,tot=0;
LL sum[N];
void dfs(int now,int pre,LL dep){
    f[now]=dep;
    tot+=f[now];
    siz[now]=1;
    sum[now]=f[now];
    for(auto k:v[now]){
        if(k==pre)continue;
        dfs(k,now,dep+1);
        siz[now]+=siz[k];
        //算一下子树大小
        sum[now]+=sum[k];
        //算一下子树的深度之和
        sum[now]%=mod;
    }
}
void dfs1(int now,int pre){
    LL x=1ll*siz[now]*(siz[now]-1)/2;
    LL mid=0;
    int sta=0;
    int G=0;
    for(auto k:v[now]){
        if(k==pre)continue;
        x=x-1ll*siz[k]*(siz[k]-1)/2;
        if(sta)ans=ans-4ll*(sum[k]*G%mod+1ll*siz[k]*mid%mod)%mod*f[now]%mod,ans=(ans+100ll*mod)%mod;
        //特别注意这地方的计算，k这个子树上的所有点都被加了G次，每个点都会加一个mid，和起来就是这么多
        mid+=sum[k];
        sta=1;
        G+=siz[k];
        //更新一下mid，G，sta
        mid%=mod;
        ans=ans-4ll*f[now]%mod*((1ll*siz[k]*f[now]%mod+sum[k])%mod)%mod;
        //这地方是以now为lca，在k这个子树上选一个点时候的贡献。
        ans=ans+100ll*mod;ans%=mod;
        dfs1(k,now);
    }
    ans=ans+4ll*x%mod*f[now]%mod*f[now]%mod;ans%=mod;
    //这里是多少对{x,y} 的lca是now，算一下贡献
}
int main() {
    scanf("%d",&n);
    for (int i=1;i<n;i++) {
        int s,t;
        scanf("%d%d",&s,&t);
        v[s].pb(t);
        v[t].pb(s);
    }
    dfs(1,0,0);
    for(int i=1;i<=n;i++){
        ans+=1ll*f[i]*f[i]%mod*(n-1)%mod;
        //这是第一部分
        ans+=2ll*f[i]*((tot-f[i])%mod)%mod;
        //这是第二部分
        ans%=mod;
        tot-=f[i];
    }
    dfs1(1,0);
    ans=ans*2ll%mod;
    //因为之前算的是一半，所以要*2
    ans=(ans+100ll*mod)%mod;
    printf("%lld\n",ans);
    return 0;
}