文档章节

BZOJ5293:[BJOI2018]求和(LCA,差分)

o
 osc_z1hvg4cu
发布于 2018/04/24 18:30
字数 863
阅读 10
收藏 0

精选30+云产品,助力企业轻松上云!>>>

Description

master 对树上的求和非常感兴趣。他生成了一棵有根树,并且希望多次询问这棵树上一段路径上所有节点深度的k
 次方和,而且每次的k 可能是不同的。此处节点深度的定义是这个节点到根的路径上的边数。他把这个问题交给
了pupil,但pupil 并不会这么复杂的操作,你能帮他解决吗?

Input

第一行包含一个正整数n ,表示树的节点数。
之后n-1 行每行两个空格隔开的正整数i,j ,表示树上的一条连接点i 和点j 的边。
之后一行一个正整数m ,表示询问的数量。
之后每行三个空格隔开的正整数i,j,k ,表示询问从点i 到点j 的路径上所有节点深度的k 次方和。
由于这个结果可能非常大,输出其对998244353 取模的结果。
树的节点从1 开始标号,其中1 号节点为树的根。

Output

对于每组数据输出一行一个正整数表示取模后的结果。
1≤n,m≤300000,1≤k≤50

Sample Input

5
1 2
1 3
2 4
2 5
2
1 4 5
5 4 45

Sample Output

33
503245989
说明
样例解释
以下用d(i) 表示第i 个节点的深度。
对于样例中的树,有d(1)=0,d(2)=1,d(3)=1,d(4)=2,d(5)=2。
因此第一个询问答案为(2^5 + 1^5 + 0^5) mod 998244353 = 33
第二个询问答案为(2^45 + 1^45 + 2^45) mod 998244353 = 503245989。

Solution

最近好没状态,感觉要钦定退役了
对于这个题,如果不考虑k次方的话就是裸的树上差分
然后发现k非常小,就可以把所有k次方的情况全部记录下来
全WA到取模和longlong上了……

Code

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #define MOD (998244353)
 5 #define N (300000+100)
 6 using namespace std;
 7 
 8 struct node
 9 {
10     int to,next;
11 }edge[N*2];
12 int Father[N],a[N],Depth[N],f[N][21],Sum[N][52],Pow[N][52];
13 int head[N],num_edge,n,m,x,y,k;
14 
15 void add(int u,int v)
16 {
17     edge[++num_edge].to=v;
18     edge[num_edge].next=head[u];
19     head[u]=num_edge;
20 }
21 
22 void Build(int x)
23 {
24     Depth[x]=Depth[Father[x]]+1;
25     Sum[x][0]=1; Pow[x][0]=1;
26     for (int i=1; i<=50; ++i) 
27     {
28         Pow[x][i]=((long long)Pow[x][i-1]*(long long)Depth[x])%MOD;
29         Sum[x][i]=(Sum[Father[x]][i]+Pow[x][i])%MOD;
30     }
31     
32     for (int i=head[x]; i; i=edge[i].next)
33         if (edge[i].to!=Father[x])
34         {
35             Father[edge[i].to]=x;
36             f[edge[i].to][0]=x;
37             Build(edge[i].to);
38         }
39 }
40 
41 int LCA(int x,int y)
42 {
43     int ans=0;
44     if (Depth[x]<Depth[y]) swap(x,y);
45     for (int i=19; i>=0; --i)
46         if (Depth[f[x][i]]>=Depth[y])
47             x=f[x][i];
48     if (x==y) return x;
49     for (int i=19; i>=0; --i)
50         if (f[x][i]!=f[y][i])
51             x=f[x][i],y=f[y][i];
52     return Father[x];
53 }
54 
55 int main()
56 {
57     scanf("%d",&n);
58     for (int i=1; i<=n-1; ++i)
59     {
60         scanf("%d%d",&x,&y);
61         add(x,y); add(y,x);
62     }
63     Depth[0]=-1;
64     Build(1);
65     for (int i=1; i<=19; ++i)
66         for (int j=1;j<=n;++j)
67             f[j][i]=f[f[j][i-1]][i-1];
68     scanf("%d",&m);
69     for (int i=1; i<=m; ++i)
70     {
71         scanf("%d%d%d",&x,&y,&k);
72         int lca=LCA(x,y);
73         printf("%d\n",((Sum[x][k]+Sum[y][k]-Sum[Father[lca]][k]-Sum[lca][k])%MOD+MOD)%MOD);
74     }
75 }
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
【BZOJ5293】[BJOI2018]求和(前缀和,LCA)

【BZOJ5293】[BJOI2018]求和(前缀和,LCA) 题面 BZOJ洛谷 题解 送分题???预处理一下$k$次方的前缀和。然后求个$LCA$就做完了?、、、

osc_04m3ui45
2019/02/13
2
0
bzoj5293: [Bjoi2018]求和(Lca)

题目传送门 。 解法: k<=50 暴力算每个点到根的每个次方和。 然后求出lca差分减一下 代码实现:

Hanks_o
2018/04/18
0
0
BJOI2018

大佬:这些题都太水啦,随随便便就AK啦 我:BJ考的都是些什么神仙题啊??? D1t1[BJOI2018]二进制 听说是结论题 我推了一个结论然后YY了一个线段树做法打了200+弃疗了打了个暴力,最后发现结...

osc_mervd488
2018/04/23
0
0
NOI模拟(5.10) BJOID1T3 求和 (bzoj5293)

求和 题目背景: 5.10 模拟 BJOI2018D1T3 分析:LCA 当时一看到被吓了一跳,这是要斯特林数还是要拉格朗日差值啊,然后看到k <= 50的时候,脸上就只剩下了一个滑稽······直接用sum[i][...

scarlyw
2018/05/12
0
0
[BJOI2018]求和

题目大意:   一个$n(nle3times10^5)$个结点的有根树。$m(mle3times10^5)$次询问,每次询问$x,y$路径上所有结点深度$k(kle50)$次方和。 思路:   树上前缀和+LCA即可。 1 #include<cstdi...

osc_at2qbd5n
2018/04/17
1
0

没有更多内容

加载失败,请刷新页面

加载更多

设计模式(4) 建造者模式

什么是建造者模式 经典建造者模式的优缺点 对建造者模式的扩展 什么是建造者模式 建造者模式将一个复杂的对象的构建与它的表示分离,使得同样的构建过程可以创建不同的表示。创建者模式隐藏了...

zhixin9001
26分钟前
14
0
ArrayList源码分析 —— JDK8

ArrayList的特性 ArrayList内部使用数据作为存储结构,ArrayList可以理解为数组的扩展对象,封装了常用的和非常用的操作数组的方法。以及当数组长度不足以保存数组时,自动扩容数组,通常Arr...

XuePeng77
33分钟前
32
0
__slots__的用法? - Usage of __slots__?

问题: Python中__slots__的目的是什么-尤其是关于何时以及何时不使用它的目的? 解决方案: 参考一: https://stackoom.com/question/1ymu/slots-的用法 参考二: https://oldbug.net/q/1ym...

富含淀粉
44分钟前
17
0
Python分析42年高考数据,告诉你高考为什么这么难?

作者:徐麟 历年录取率 可能很多经历过高考的人都不知道高考的全称,高考实际上是普通高等学校招生全国统一考试的简称。从1977年国家恢复高考制度至今,高考经历了许多的改革,其中最为显著的...

爱码小哥
45分钟前
19
0
CKEditor 5 + SpringBoot实战(四):SpringBoot 实现文件上传

在本系列的文章中,我将介绍如何在Spring Boot Application中使用CKEditor编辑器。介绍的内容包括基本环境的搭建,文件上传,SpringData JPA数据持久化,CKEditor5的安装,CKEditor图片上传,...

树下魅狐
47分钟前
20
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部