发布于  更新于 

洛谷P4427 [BJOI2018]求和

LCA 题解 OI

好久都没有发过新文章了,水一点题解吧

这道题乍一看好像是数学题,但观察到 ,就可以预处理处每个k对应的树上前缀和,就很好办了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
// luogu-judger-enable-o2
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

typedef long long int64;
const int MAXN = 300010;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;

class LFS {
public:
LFS() {
memset(head, -1, sizeof head);
ecnt = 0;
n = 0;
}
LFS(int N) {
memset(head, -1, sizeof head);
ecnt = 0;
n = N;
}
void adde(int from, int to, int w) {
e[ecnt].to = to;
e[ecnt].w = w;
e[ecnt].next = head[from];
head[from] = ecnt++;
}
void addde(int a, int b, int w) {
adde(a, b, w);
adde(b, a, w);
}

protected:
struct Edge {
int to, next, w;
} e[MAXN * 2];
int head[MAXN];
int ecnt;
int n;

private:
virtual void dfs(int u, int fa) {
for (int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].to;
if (v != fa) {
dfs(v, u);
}
}
}
};

int64 pow_mod(int64 a, int64 b) {
int64 res = 1;
while (b) {
if (b & 1) res = res * a % MOD;
a = a * a % MOD;
b /= 2;
}
return res;
}

class LCA : public LFS{
public:
int dep[MAXN];
int64 sum[MAXN][51];
LCA(int n) : LFS(n) {
memset(dep, -1, sizeof dep);
memset(sum,0,sizeof sum);
}
void pre(int rt = 1) { dfs(rt, 0, 0); }
int querylca(int a, int b) {
if (dep[a] > dep[b]) swap(a, b);
int h = dep[b] - dep[a];
for (int i = 20; i >= 0; i--) {
if(h & (1 << i)) {
b = f[b][i];
}
}
if (a == b) return a;
for (int i = 20; i >= 0; i--) {
if (f[a][i] == f[b][i]) continue;
a = f[a][i];
b = f[b][i];
}
return f[a][0];
}

//protected:
int f[MAXN][22];

private:
void dfs(int u, int d, int fa) {
dep[u] = d;
f[u][0] = fa;
for(int i = 1;i<=50;i++){
sum[u][i] = sum[fa][i] + pow_mod(d,i);
sum[u][i] %= MOD;
}
for (int i = 1; i < 21; i++) {
f[u][i] = f[f[u][i - 1]][i - 1];
}
for (int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].to;
if (dep[v] == -1) {
dfs(v, d + 1, u);
}
}
}
};

#include <cctype>
#include <cstdio>

inline int read() {
int X = 0, w = 0;
char ch = 0;
while (!isdigit(ch)) {
w |= ch == '-';
ch = getchar();
}
while (isdigit(ch)) {
X = (X << 3) + (X << 1) + (ch ^ 48);
ch = getchar();
}
return w ? -X : X;
}

int main(){
int n = read();
LCA* tree = new LCA(n);
for(int i = 1;i<n;i++){
int u = read();
int v = read();
tree->addde(u,v,1);
}
tree->pre();
int m = read();
for(int i = 1;i<=m;i++){
int a = read();
int b = read();
int k = read();
int lca = tree->querylca(a,b);
cout << ((tree->sum[a][k] + tree->sum[b][k] - tree->sum[lca][k] - tree->sum[tree->f[lca][0]][k])%MOD + MOD)%MOD << endl;
}
}

要特别注意题目要统计的是点权不是边权,因此小心前缀和重复计算LCA的值。