树 ( 树形结构 + 数学 )
程序员文章站
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;
}
上一篇: 万事开头难 百度竞价账户搭建要好好研究
推荐阅读
-
数据结构_图的应用_最小生成树1(普里姆算法)
-
[PHP] 算法-二叉树的子结构判断的PHP实现
-
THINKPHP3.2.3含有树形结构的无限分类的实现
-
洛谷P4588 [TJOI2018]数学计算(线段树)
-
php:树形结构的算法_PHP教程
-
Codeforces Round #482 (Div. 2) D. Kuro and GCD and XOR and SUM(数学+01字典树)(好题)
-
php实现的树形结构数据存取类实例,树形实例_PHP教程
-
python django 多级业务树形结构规划及页面渲染
-
数据结构学习笔记(3)——树
-
关于树型结构的表,在hibernate中如何配置。 HibernateJavaAccess