题解 P5305 【[GXOI/GZOI2019]旧词】

## [原文地址](https://www.cnblogs.com/bcoier/p/10788658.html) ### 前置芝士：[[LNOI2014]LCA](https://www.luogu.org/problemnew/show/P4211) ~~要是这题放HNOI就好了~~ 原题：$\sum_{l≤i≤r}dep[LCA(i,z)]$ 这题：$\sum_{i≤r}dep[LCA(i,z)]^k$ 对于原题，我们需要把每个询问拆成1~l-1 & 1~r再进行差分（~~所以这题帮我们省去了一个步骤~~） ### 先考虑$k=1$~~原题~~ 我们先转化题意 $dep[lca]\ ==\ dis[1][lca]+1\ ==\ lca->1$的点数 所以我们每一个点(x)对答案的贡献($dep[lca(x, z)]$)，就是他们到根节点的公共路径的点数 于是，对于每一个点，我们只需要把1->x的链上加1即可 对于每一个询问，我们只需要求出1->z的链上的和即可 这一点我们可以利用树剖$/LCT$解决 但是直接做是$O(N^2*$树剖/$LCT)$的，我们考虑莫队 这样复杂度变成了$O(N\sqrt{N}*$树剖/$LCT)$ ~~什么？你觉得这个算法还不够优秀？所以我们来考虑优化莫队~~ 莫队的$\sqrt{N}$是怎么来的？不停的移动左右端点 但是这道题的左端点是固定的$(1)$，所以只需要移动右端点即可，而右端点不需要动来动去，只需要往后扫一遍即可，复杂度是$O(N*$树剖/$LCT)$ 代码的话可以参考[[LNOI2014]LCA](https://www.luogu.org/problemnew/show/P4211) ### 考虑k!=1 我们为什么k=1的时候对于每个点是$1->x$路径上+1？ 这个1的本质是树上差分，即：$(dep[x]+1)^1-dep[x]^1 = 1$ 所以我们只需要把1改成k即可 所以现在问题变成了：给定一个序列，每一个点有两个权值$(a, b)$，每一个点的点权为$a*b$，支持a权值区间加1和区间查询 因为b不会改变，所以我们考虑线段树 把线段树的每一个节点新弄一个权值，为$\sum_{l≤i≤r} b$，每次更新区间的时候用这个权值$\times sum$即可 ``` #include<bits/stdc++.h> using namespace std; #define il inline #define re register #define debug printf("Now is Line : %d\n",__LINE__) #define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout) #define int long long #define inf 123456789 #define mod 998244353 il int read() { re int x = 0, f = 1; re char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return x * f; } #define rep(i, s, t) for(re int i = s; i <= t; ++ i) #define Next(i, u) for(re int i = head[u]; i; i = e[i].next) #define mem(k, p) memset(k, p, sizeof(k)) #define ls k * 2 #define rs k * 2 + 1 #define _ 500005 struct edge {int v, next;}e[_]; struct ques { int u, z, id; il bool operator < (const ques x) const {return u < x.u;} }q[_]; int n, m, k, val[_ << 2], sum[_ << 2], mi[_], head[_], cnt, ans[_], tag[_ << 2], now; int fa[_], dep[_], size[_], son[_], top[_], seg[_], col, rev[_]; il void add(int u, int v) { e[++ cnt] = (edge) {v, head[u]}, head[u] = cnt; } il int qpow(int a, int b) { int r = 1; while(b) { if(b & 1) r = 1ll * r * a % mod; b >>= 1, a = 1ll * a * a % mod; } return r; } il void dfs1(int u) { dep[u] = dep[fa[u]] + 1, size[u] = 1; Next(i, u) { if(e[i].v == fa[u]) continue; dfs1(e[i].v), size[u] += size[e[i].v]; if(size[son[u]] < size[e[i].v]) son[u] = e[i].v; } } il void dfs2(int u, int fr) { top[u] = fr, seg[u] = ++ col, rev[col] = u; if(son[u]) dfs2(son[u], fr); Next(i, u) if(e[i].v != son[u] && e[i].v != fa[u]) dfs2(e[i].v, e[i].v); } il void build(int k, int l, int r) { if(l == r) return (void)(val[k] = (mi[dep[rev[l]]] - mi[dep[rev[l]] - 1] + mod) % mod); int mid = (l + r) >> 1; build(ls, l, mid), build(rs, mid + 1, r), val[k] = (val[ls] + val[rs]) % mod; } il void pushdown(int k) { if(!tag[k]) return; sum[ls] = (sum[ls] + ((tag[k] * val[ls]) % mod)) % mod; sum[rs] = (sum[rs] + ((tag[k] * val[rs]) % mod)) % mod; tag[ls] += tag[k], tag[rs] += tag[k], tag[k] = 0; } il void change(int k, int l, int r, int ll, int rr) { if(l > rr || ll > r) return; if(l >= ll && r <= rr) {sum[k] = (sum[k] + val[k]) % mod, ++ tag[k]; return;} int mid = (l + r) >> 1; pushdown(k), change(ls, l, mid, ll, rr), change(rs, mid + 1, r, ll, rr); sum[k] = (sum[ls] + sum[rs]) % mod; } il int query(int k, int l, int r, int ll, int rr) { if(l > rr || ll > r) return 0; if(l >= ll && r <= rr) return sum[k]; int mid = (l + r) >> 1; pushdown(k); return (query(ls, l, mid, ll, rr) + query(rs, mid + 1, r, ll, rr)) % mod; } il int query(int u) { int ans = 0; while(top[u]) ans = (ans + query(1, 1, n, seg[top[u]], seg[u])) % mod, u = fa[top[u]]; return ans; } il void change(int u) { while(top[u]) change(1, 1, n, seg[top[u]], seg[u]), u = fa[top[u]]; } signed main() { n = read(), m = read(), k = read() % (mod - 1), now = 1; rep(i, 1, n) mi[i] = qpow(i, k); rep(i, 2, n) fa[i] = read(), add(fa[i], i); rep(i, 1, m) q[i].id = i, q[i].u = read(), q[i].z = read(); sort(q + 1, q + m + 1), dfs1(1), dfs2(1, 1), build(1, 1, n); rep(i, 1, n) { change(i); while(i == q[now].u) ans[q[now].id] = query(q[now].z), ++ now; } rep(i, 1, m) printf("%lld\n", ans[i]); return 0; } ```