欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

树 ( 树形结构 + 数学 )

程序员文章站 2022-06-08 16:38:22
...

题目链接
树 ( 树形结构 + 数学 )

解题报告:
转载自:大佬博客

#define first f
#define second s
#define ll long long
#define mp make_pair
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#include <bits/stdc++.h>
#define pii pair<int,int>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn=1e6+5;
const int inf=0x3f3f3f3f;
const int MOD=998244353;
const double PI=acos(-1);
const double e=2.718281828459;

pii p[maxn<<1];
int head[maxn<<1],cnt,sz[maxn],deep[maxn];
ll sum[maxn],ans=0,res=0,ant=0;
void add(int from,int to)
{
    p[++cnt].s=head[from];
    p[cnt].f=to;
    head[from]=cnt;
}
void dfs(int now,int pre)
{
    deep[now]=deep[pre]+1,sz[now]=1;sum[now]=deep[now];
    ant=(ant+1ll*deep[now]*deep[now]%MOD)%MOD;
    for(int i=head[now];~i;i=p[i].s){
        int to=p[i].f;
        if(to==pre){continue;}
        dfs(to,now);
        sz[now]=(sz[now]+sz[to])%MOD;
        sum[now]=(sum[now]+sum[to])%MOD;
    }
}
void DFS(int now,int pre)
{
    ll csum=0,ksum=0;
    for(int i=head[now];~i;i=p[i].s){
        int to=p[i].f;
        if(to==pre){continue;}
        csum=(csum+1ll*sz[to]*sz[to]%MOD)%MOD;
        ksum=(ksum+2ll*sum[to]*(sz[now]-sz[to])%MOD)%MOD;
        DFS(to,now);
    }
    ksum=(ksum+2ll*deep[now]*sz[now]%MOD)%MOD;
    csum=(1ll*sz[now]*sz[now]%MOD-csum+MOD)%MOD;
    ans=(ans+4ll*deep[now]*deep[now]%MOD*csum%MOD)%MOD;
    ans=(ans-4ll*deep[now]*ksum%MOD+MOD)%MOD;
}
int main()
{
    mem(head,-1);
    int n,u,v;
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    dfs(1,0);
    DFS(1,0);
    ans=(ans+ant*sz[1]*2%MOD)%MOD;
    ans=(ans+sum[1]*sum[1]*2%MOD)%MOD;
    printf("%lld\n",ans);
    return 0;
}

相关标签: 树形结构