【HNOI2015】开店

hychyc

2018-09-03 19:32:09

Solution

## 题目描述 题目大意:给定一颗$n(n\leq150000)$个点的树,每个点有点权,边有边权(表示两个点之间的距离)。$q(q\leq200000)$次询问,每次询问点权在$[L, R]$之间的所有点到某个点的距离之和。强制在线。 ## 分析 首先考虑一个简化的版本,询问所有点到点$u$的距离和。尝试进行公式推导。 令$dep[i], size[i]$分别表示以$1$为根时第$i$个点的深度和子树大小。观察$1$为根和$u$为根会发生哪些变化。 $u$的子树中某节点$v$的深度会从$dep[v]$变成$dep[v]-dep[u]$,相当于都减少了$dep[u]$,且有$size[u]个点发生了此变化$;$fa[u]$的子树,且不是$u$的子树中的某节点$v$,深度会从$dep[v]$变成$dep[v]-dep[fa[u]]+dep[u]-dep[fa[u]]$,相当于减少了$2dep[fa[u]]-dep[u]$,且有$size[fa[u]]-size[u]$个点发生了此变化,以此类推。 更具体的描述,定义$a_{i}$为$1$至$u$的链上的第$i$个点,$1$至$u$的链上共有$k$个点,那么所有点到$u$的距离之和可以用如下式子表示: $\sum_{i=1}^{n}dep[i] - \sum_{i=1}^{k-1}(size[a_{i}]-size[a_{i+1}])*(2*dep[a_{i}]-dep[u])-size[u]*dep[u]$ 展开可得: $\sum_{i=1}^{n}dep[i]- size[u]*dep[u]-$ $(2*\sum_{i=1}^{k-1}size[a_{i}]*dep[a_{i}]-$ $2*\sum_{i=1}^{k-1}size[a_{i+1}]*dep[a_{i}]-$ $\sum_{i=1}^{k-1}size[a_{i}]*dep[u]+$ $\sum_{i=1}^{k-1}size[a_{i+1}]*dep[u])$ $=\sum_{i=1}^{n}dep[i]- size[u]*dep[u]-$ $2*\sum_{i=1}^{k-1}size[a_{i}]*dep[a_{i}]+$ $2*\sum_{i=1}^{k-1}size[a_{i+1}]*dep[a_{i}]+$ $\sum_{i=1}^{k-1}size[a_{i}]*dep[u]$ $\sum_{i=1}^{k-1}size[a_{i+1}]*dep[u])$ 其中 $\sum_{i=1}^{k-1}size[a_{i}]*dep[u]-\sum_{i=1}^{k-1}size[a_{i+1}]*dep[u] $ $= \sum_{i=1}^{k-1}size[a_{i}]*dep[u]-\sum_{i=2}^{k}size[a_{i}]*dep[u]$ $ = size[a_{1}]*dep[u] -size[a_{k}]*dep[u]= n*dep[u]-size[u]*dep[u]$ 于是原式变为 $\sum_{i=1}^{n}dep[i] +n*dep[u]-2*size[u]*dep[u] $ $- 2*\sum_{i=1}^{k-1}size[a_{i}]*dep[a_{i}]+2*\sum_{i=1}^{k-1}size[a_{i+1}]*dep[a_{i}]$ 现在观察 $- 2*\sum_{i=1}^{k-1}size[a_{i}]*dep[a_{i}]+2*\sum_{i=1}^{k-1}size[a_{i+1}]*dep[a_{i}] $ $= 2*\sum_{i=1}^{k-1}size[a_{i+1}]*dep[a_{i}]- 2*\sum_{i=1}^{k-1}size[a_{i}]*dep[a_{i}]$ 直接相减出现的$size[a_{i}]-size[a_{i+1}]$难以处理,我们考虑进行一次错位 原式$=2*\sum_{i=2}^{k}size[a_{i}]*dep[a_{i-1}]- 2*\sum_{i=1}^{k-1}size[a_{i}]*dep[a_{i}]$ $=2*\sum_{i=2}^{k}size[a_{i}]*dep[a_{i-1}]- 2*\sum_{i=2}^{k-1}size[a_{i}]*dep[a_{i}] (dep[a_{1}]=dep[1]=0)$ $=2*size[a_{k}]*dep[a_{k-1}] + 2*\sum_{i=2}^{k-1}size[a_{i}]*(dep[a_{i-1}]-dep[a_{i}])$ 将原式中的$-2*size[u]*dep[u]$并入上式中,得到: $2*size[a_{k}]*dep[a_{k-1}] -2*size[a_{k}]*dep[a_k]$ $+ 2*\sum_{i=2}^{k-1}size[a_{i}]*(dep[a_{i-1}]-dep[a_{i}])$ $=2*\sum_{i=2}^{k}size[a_{i}]*(dep[a_{i-1}]-dep[a_{i}])$ 注意到$dep[a_i]-dep[a_{i-1}]$是点 $i$ 到其父节点的边权,定义为$fv[i]$ 故原式等于 $\sum_{i=1}^{n}dep[i] +n*dep[u]-2*\sum_{i=2}^{k}size[a_{i}]*fv[a_i]$ 可以进行维护 现在考虑如何加入$[L, R]$的限制。直接通过子树查询的方式进行,单次复杂度与树高约为线性关系,不可以接受。这时便要体会主席树的版本作用。 将点按照点权排序,一个一个加入,最终答案便是$R$对应版本的主席树的答案减去$L$个对应版本的前一个版本的主席树的答案。 每次加入一个点的时候,树的形态不发生变化,$fv[i]$不发生变化,只有$size[i]$发生变化。只需把加入的这个点到根的路径上的所有点的$size$进行$+1$即可,查询时从当前指定的点出发,向上统计$\sum size[i]*fv[i]$。这是可以通过树链剖分维护的。由于空间限制,标记永久化是一个不错的选择。 ## 思路总结 对主席树的认识不要僵化,体会其有关版本的作用。例如对于区间$[l, r]$统计在$[L, R]$之间的数的个数问题,其实也可以按照数值排序后一个个插入点,统计第$R$个版本的树中位置是$[l, r]$的有多少,减去第$L-1$颗树的答案。不同版本不一定是按照位置,也不一定是按照权值(虽然我目前就见过这俩),思路要灵活。 ## 代码 ``` #include <iostream> #include <cstdio> #include <cstring> #include <bits/stdc++.h> #define MAXN 200050 #define ri register int #define il inline using namespace std; typedef long long LL; int n, q, A, ecnt, numcnt, root[MAXN], rtcnt, num[MAXN]; int tcnt, top[MAXN], id[MAXN], fa[MAXN], fv[MAXN], son[MAXN], size[MAXN]; LL lastans, dsum[MAXN], dep[MAXN]; struct Node { int id, ag; bool operator < (const Node &x) const { if(ag == x.ag) return id < x.id; return ag < x.ag; } }mon[MAXN]; struct node { int v, w; node *next; }pool[MAXN<<2], *h[MAXN]; struct NODE { int ls, rs, lazy; LL sum, esum; void init() { ls = rs = lazy = 0, esum = sum = 0; } }t[MAXN<<7]; il void adde(int u, int v, int w) { node *p = &pool[ecnt++], *q = &pool[ecnt++]; *p = node {v, w, h[u]}, h[u] = p; *q = node {u, w, h[v]}, h[v] = q; } void dfs1(int u) { size[u] = 1; for(node *p = h[u]; p; p = p->next) { if(p->v == fa[u]) continue; dep[p->v] = dep[u]+p->w, fa[p->v] = u, fv[p->v] = p->w, dfs1(p->v), size[u] += size[p->v]; if(size[p->v] > size[son[u]]) son[u] = p->v; } } void dfs2(int u, int t) { id[u] = ++tcnt, top[u] = t, num[tcnt] = fv[u]; if(!son[u]) return ; dfs2(son[u], t); for(node *p = h[u]; p; p = p->next) if(!id[p->v]) dfs2(p->v, p->v); } void build(int &u, int l, int r) { int tmp = u; u = ++rtcnt, t[u] = t[tmp]; if(l == r) return (void)(t[u].esum = num[l]); int mid = (l+r)>>1; build(t[u].ls, l, mid); build(t[u].rs, mid+1, r); t[u].esum = t[t[u].ls].esum + t[t[u].rs].esum; } void change(int &u, int l, int r, int tl, int tr) { int tmp = u; u = ++rtcnt, t[u] = t[tmp]; if(tl <= l && r <= tr) { ++t[u].lazy; t[u].sum += t[u].esum; return ; } int mid = (l+r)>>1; if(tl <= mid) change(t[u].ls, l, mid, tl, tr); if(mid < tr) change(t[u].rs, mid+1, r, tl, tr); t[u].sum = t[t[u].ls].sum + t[t[u].rs].sum + t[u].esum*t[u].lazy; } void Change(int u, int ver) { while(top[u] != 1) { change(root[ver], 1, n, id[top[u]], id[u]); u = fa[top[u]]; } change(root[ver], 1, n, 1, id[u]); } LL query(int u, int l, int r, int tl, int tr, int add) { if(tl <= l && r <= tr) return t[u].sum + t[u].esum*add; int mid = (l+r)>>1; LL ret = 0; add += t[u].lazy; if(tl <= mid) ret += query(t[u].ls, l, mid, tl, tr, add); if(mid < tr) ret += query(t[u].rs, mid+1, r, tl, tr, add); return ret; } LL Query(int u, int ver) { LL ret = 0; while(top[u] != 1) { ret += query(root[ver], 1, n, id[top[u]], id[u], 0); u = fa[top[u]]; } ret += query(root[ver], 1, n, 1, id[u], 0); return ret; } il LL calc(int u, int ver) { return dsum[ver] + ver*dep[u] - 2*Query(u, ver); } int main() { int u, v, c; scanf("%d%d%d", &n, &q, &A); for(ri i = 1; i <= n; ++i) scanf("%d", &mon[i].ag), mon[i].id = i; for(ri i = 1; i < n; ++i) scanf("%d%d%d", &u, &v, &c), adde(u, v, c); dfs1(1), dfs2(1, 1); sort(mon+1, mon+n+1); build(root[0], 1, n); for(ri i = 1; i <= n; ++i) dsum[i] = dsum[i-1] + dep[mon[i].id], root[i] = root[i-1], Change(mon[i].id, i); while(q--) { LL l, r; int L, R; scanf("%d%lld%lld", &u, &l, &r); l += lastans, r += lastans; L = min(l%A, r%A), R = max(l%A, r%A); L = lower_bound(mon+1, mon+n+1, Node{0, L})-mon, R = upper_bound(mon+1, mon+n+1, Node{MAXN, R})-mon-1; printf("%lld\n", lastans = calc(u, R)-calc(u, L-1)); } return 0; } ```