洛谷 P4427 求和
2024-10-14 19:40:58
传送门啦
思路:
开始不肿么容易想到用倍增,但是想到需要求 $ Lca $ ,倍增这种常数小而且快的方法就很方便了。求 $ Lca $ 就是一个最普通的板子。那现在考虑怎么求题目中的结果。
树上差分可能听起来很高大上,但是前缀和并不陌生,树上差分就理解成树上前缀和就好了:
$ sum[u] + sum[v] - sum[lca(u , v)] ; $
树上差分之前要先预处理出 $ dis $ 数组, $ dis[i][j] $ 表示从 $ i $ 出发到根节点(本题中的1号节点)的 $ j $ 次方。
for(re long long j = 1 ; j <= 50 ; ++ j)
dis[x][j] = dis[fa][j] + quick_power(dep[x] , j) ;
这就是预处理的代码了, $ dep $ 表示深度 , $ quick - power $ 为快速幂。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#define re register
using namespace std ;
const long long maxn = 300005 ;
const long long mod = 998244353 ;
inline long long read () {
long long f = 1 , x = 0 ;
char ch = getchar () ;
while(ch > '9' || ch < '0') {if(ch == '-') f = -1 ; ch = getchar () ;}
while(ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch - '0' ; ch = getchar () ;}
return x * f ;
}
inline void print (long long x){
if(x < 0) {putchar('-') ; x = -x ;}
if(x > 9) print(x / 10) ;
putchar(x % 10 + '0') ;
}
long long n , x , y , m , a , b , c ;
long long head[maxn] , tot ;
long long ans ;
struct Edge {
long long from , to , next ;
}edge[maxn << 1] ;
inline void add (long long u , long long v) {
edge[++tot].from = u ;
edge[tot].to = v ;
edge[tot].next = head[u] ;
head[u] = tot ;
}
long long quick_power (long long a , long long b) {
long long res = a , ans = 1 ;
while(b) {
if(b & 1) ans = ans * res % mod ;
res = res * res % mod ;
b >>= 1 ;
}
return ans % mod ;
}
long long dep[maxn] , f[maxn][21] , dis[maxn][51];
inline void dfs (long long x , long long fa) {
dep[x] = dep[fa] + 1 ;
f[x][0] = fa ;
for(re long long j = 1 ; j <= 50 ; ++ j)
dis[x][j] = dis[fa][j] + quick_power(dep[x] , j) ;
for(re long long i = 1 ; (1 << i) <= dep[x] ; ++ i) {
f[x][i] = f[f[x][i - 1]][i - 1] ;
}
for(re long long i = head[x] ; i ; i = edge[i].next) {
long long v = edge[i].to ;
if(v != fa) dfs(v , x) ;
}
}
inline long long lca (long long a , long long b) {
if(dep[a] < dep[b]) swap(a , b) ;
for(re long long i = 20 ; i >= 0 ; -- i) {
if((1 << i) <= (dep[a] - dep[b]) ) {
a = f[a][i] ;
}
}
if(a == b) return a ;
for(re long long i = 20 ; i >= 0 ; -- i) {
if((1 << i) <= dep[a] && (f[a][i] != f[b][i])) {
a = f[a][i] ;
b = f[b][i] ;
}
}
return f[a][0] ;
}
int main () {
n = read () ;
for(re long long i = 1 ; i <= n - 1 ; ++ i) {
x = read () ; y = read () ;
add(x , y) ;
add(y , x) ;
}
dep[1] = -1 ;
dfs(1 , 1) ;
m = read () ;
for(re long long i = 1 ; i <= m ; ++ i) {
a = read () ; b = read () ; c = read () ;
long long root = lca(a , b) ;
ans = (dis[a][c] - dis[root][c] + dis[b][c] - dis[f[root][0]][c]) % mod ;
//printf("%d %d %d %d\n" , dis[a][c] , dis[b][c] , dis[root][c] , quick_power(dep[root] , c) % mod ) ;
print(ans) ;
printf("\n") ;
}
return 0 ;
}
最新文章
- usr类库的使用(一般用在第三方类库使用系统库报错头文件找不到时)
- 阿里云 SWAP
- ssh连接速度慢解决
- Qt OpenCV Support Image Type 支持读写的图像格式
- 使用TCP协议的NAT穿透技术
- FAILURE: Build failed with an exception. Crunching Cruncher screen.png failed
- Computer Vision Algorithm Implementations
- [EXCEL] 在单元格中自动输入时间和日期
- JavaScript面向对象之类的继承
- HBASE完全分布式模式的安装
- 微信小程序 获取OpenId
- 2018/1/21 Netty通过解码处理器和编码处理器来发送接收POJO,Zookeeper深入学习
- Android官方技术文档翻译——清单合并
- OpenFlow Flow-Mod消息学习
- IO的详细解释:It&#39;s all about buffers: zero-copy, mmap and Java NIO
- 记一次AngularJs 路由 $stateChangeStart不起作用(细节决定成败)
- CC3000 Arduino 连接Yeelink中文注释 示例
- 使用keepalived实现双机热备
- 2018.09.26洛谷P1084 疫情控制(二分+倍增)
- Windows Server 2008 R2 web服务器发布在线系统时遇到的问题
热门文章
- python---正则中的(?P<;name>;group)
- Code::Blocks代码自动提示设置及常用快捷键
- bzoj千题计划307:bzoj5248: [2018多省省队联测]一双木棋
- GUI之ScrollView的使用
- Linux 命令详解(六)Linux 守护进程的启动方法
- Hibernate_day01
- Netty 实现HTTP文件服务器
- Python分析网页中的<;a>;标签
- Bulma - 基于 Flexbox 的现代化的 CSS 框架
- SQL语句——重复记录