题解 P5305 【[GXOI/GZOI2019]旧词】
GKxx
2019-04-22 17:46:45
来个稍微有点不一样的
其实大体思路大家都已经讲得比较到位了
就是把[LNOI2014]LCA那题改一改，把加$1$改成加$k$次差分
可是询问离线什么的最讨厌了
我这种懒人当然是写可持久化线段树了
空间要开大一点，注意标记下传的时候也要复制节点
按可持久化的方法写就行了
所以其实这题完全可以强制在线嘛！
```cpp
#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>
template <typename T> inline void read(T& x) {
int f = 0, c = getchar(); x = 0;
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
if (f) x = -x;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
read(x); read(args...);
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
}
template <typename T> inline void writeln(T x) { write(x); puts(""); }
template <typename T> inline bool chkmin(T& x, const T& y) { return y < x ? (x = y, true) : false; }
template <typename T> inline bool chkmax(T& x, const T& y) { return x < y ? (x = y, true) : false; }
typedef long long LL;
const LL mod = 998244353;
const int maxn = 5e4 + 207;
inline LL qpow(LL x, LL k) {
LL s = 1;
for (; k; x = x * x % mod, k >>= 1)
if (k & 1) s = s * x % mod;
return s;
}
int v[maxn], head[maxn], next[maxn], etot;
int dep[maxn], top[maxn], fa[maxn], size[maxn], son[maxn], dfn[maxn], arcdfn[maxn], xys;
LL s[maxn], a[maxn];
int n, q, K;
inline void ae(int x, int y) {
v[++etot] = y; next[etot] = head[x]; head[x] = etot;
}
void dfs(int x) {
dep[x] = dep[fa[x]] + 1; size[x] = 1;
for (int i = head[x]; i; i = next[i]) {
fa[v[i]] = x;
dfs(v[i]);
size[x] += size[v[i]];
if (size[v[i]] >= size[son[x]]) son[x] = v[i];
}
}
void dfs(int x, int t) {
top[x] = t; dfn[x] = ++xys; arcdfn[xys] = x;
if (son[x]) dfs(son[x], t);
for (int i = head[x]; i; i = next[i])
if (v[i] != son[x]) dfs(v[i], v[i]);
}
struct Node {
int lc, rc;
LL sum, add;
Node() : lc(0), rc(0), sum(0), add(0) {}
};
Node T[maxn << 7];
int root[maxn], tot;
inline void update(int o) {
T[o].sum = (T[T[o].lc].sum + T[T[o].rc].sum) % mod;
}
inline void pushdown(int o, int l, int mid, int r) {
if (T[o].add) {
LL &d = T[o].add;
T[++tot] = T[T[o].lc];
T[o].lc = tot;
T[++tot] = T[T[o].rc];
T[o].rc = tot;
T[T[o].lc].sum = (T[T[o].lc].sum + d * (s[mid] - s[l - 1] + mod) % mod) % mod;
T[T[o].rc].sum = (T[T[o].rc].sum + d * (s[r] - s[mid] + mod) % mod) % mod;
T[T[o].lc].add += d;
T[T[o].rc].add += d;
d = 0;
}
}
void modify(int &o, int lb, int rb, int l, int r) {
if (l > rb || r < lb) return;
T[++tot] = T[o]; o = tot;
if (l <= lb && r >= rb) {
T[o].sum = (T[o].sum + s[rb] - s[lb - 1] + mod) % mod;
++T[o].add;
return;
}
int mid = (lb + rb) >> 1;
pushdown(o, lb, mid, rb);
modify(T[o].lc, lb, mid, l, r);
modify(T[o].rc, mid + 1, rb, l, r);
update(o);
}
LL query(int o, int lb, int rb, int l, int r) {
if (!o || l > rb || r < lb) return 0;
if (l <= lb && r >= rb) return T[o].sum;
int mid = (lb + rb) >> 1;
pushdown(o, lb, mid, rb);
return (query(T[o].lc, lb, mid, l, r) + query(T[o].rc, mid + 1, rb, l, r)) % mod;
}
inline void add(int x, int i) {
for (; x; x = fa[top[x]])
modify(root[i], 1, n, dfn[top[x]], dfn[x]);
}
inline LL query(int x, int i) {
LL ans = 0;
for (; x; x = fa[top[x]])
ans = (ans + query(root[i], 1, n, dfn[top[x]], dfn[x])) % mod;
return ans;
}
int main() {
read(n, q, K);
for (int i = 2, f; i <= n; ++i)
read(f), ae(f, i);
dfs(1); dfs(1, 1);
for (int i = 1; i <= n; ++i)
a[i] = (qpow(dep[i], K) - qpow(dep[i] - 1, K) + mod) % mod;
for (int i = 1; i <= n; ++i)
s[i] = (s[i - 1] + a[arcdfn[i]]) % mod;
for (int i = 1; i <= n; ++i) {
root[i] = root[i - 1];
add(i, i);
}
while (q--) {
int x, y; read(x, y);
writeln(query(y, x));
}
return 0;
}
```