一个数据结构题, 有不优美的动态点分治做法和写起来比动态点分治还长的树链剖分+可持久化线段树做法。

思维难度: 没有?

就是代码题喽。

题目链接

题目大意

强制在线, 每个节点的妖怪(?)有一个年龄, 树上的边带权, 多次单点询问年龄在\([l,r]\)的妖怪到节点\(u\)的距离和。

解题报告

先说一个很不优美的动态树分治的做法。

记录每个点到经过的分治重心的距离, 在每个分治重心处把分治块中的点按照年龄进行排序, 查询的时候二分得到这个分支块中年龄\([l,r]\)之间的点的个数和到分治重心的距离和。

因为点分治 在每个分治重心处得到答案时, 需要减去分治树下一层在同一块的答案, 所以还需要按照下一层所在的分支块为第一关键字, 年龄为第二关键字排序, 在查询的时候减去不合法的这部分数据。

好, 现在说一个代码更长的比较优美的做法

对于询问\((u, l, r)\), 需要求的答案为\(\text{ans}\)\[ \begin{aligned} \text{ans}&=\sum_{x,\text{age}_x \in [l,r]} \text{dis}(u, x) \\ &=\sum_{x, \text{age}_x \in [l,r]} \text{dep}(u)+\text{dep}(x)-2 \times \text{dep}(\text{lca}(u,x)) \end{aligned} \] 其中\(\sum_{x, \text{age}_x \in [l,r]} \text{dep}(u)+\text{dep}(x)\)可以通过前缀相减\(O(1)\)得到。

考虑求\(\sum_{x, \text{age}_x \in [l,r]} \text{dep}(\text{lca}(u,x))\), 考虑每条边的贡献, 也就是如果有一个点\(x( \text{age}_x \in [l,r])\), 那么\(\text{lca}(u,x)\)到根的边贡献加\(1\)

做法是将\(x( \text{age}_x \in [l,r])\)到根路径上的边的贡献加\(1\), 查询\(u\)的时候,查询\(u\)到根的路径上的贡献, 就成功收集\(\text{lca}(u,x)\)到根的边贡献了。

在考虑\(\text{age}_x \in [l,r]\) 的限制, 只需要按照\(\text{age}\)把妖怪排序并依次加入,对统计贡献的线段树进行可持久化就好了。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i=int(a),nn=int(b);i<=nn;++i)
#define vep(i,a,b) for (int i=int(a),nn=int(b);i>=nn;--i)
#define xep(i,b) for (int i=0,nn=int(b);i<nn;++i)
typedef long long ll;
const int N=150010;
struct nde {
int l,r,tg,tm; ll sm;
nde(int l=0,int r=0,int tg=0,int tm=0,int sm=0)
:l(l),r(r),tg(tg),tm(tm),sm(sm){}
} v[20000000];
struct edge {
int nxt,to,c; edge(int nxt=0,int to=0,int c=0)
:nxt(nxt),to(to),c(c){}
} e[N<<1];
int n,Q,A,hsh[N],od[N],hed[N],tot,cnt;
int sz[N],sn[N],rt[N],d[N],f[N],b[N],dn[N],bd[N],ct;
ll sm[N],as,hv;
inline void in(int &x) {
char ch=getchar(); int f=1;
for (;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
for (x=0;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-48;
x*=f;
}
inline bool cmp(int x,int y) {
return hsh[x]<hsh[y];
}
inline void add(int x,int y,int c) {
e[++tot]=edge(hed[x],y,c),hed[x]=tot;
}
void dfs(int x) {
sz[x]=1,sn[x]=0; int y;
for (int i=hed[x];i;i=e[i].nxt)
if (y=e[i].to, y!=f[x]) {
f[y]=x, d[y]=d[x]+e[i].c,dfs(y);
sz[x]+=sz[y]; if(sz[y]>sz[sn[x]]) sn[x]=y;
}
}
void dfs(int x,int top) {
b[x]=top,dn[x]=++cnt,bd[cnt]=x;int y;
if (sn[x]) { dfs(sn[x],top);
for (int i=hed[x];i;i=e[i].nxt)
if (y=e[i].to, y!=f[x]&&y!=sn[x])
dfs(y,y);
}
}
inline int fd(int x) {
int l=0,r=n,md,rc=0;
while (l<=r) { md=(l+r)>>1;
if (hsh[od[md]]<=x) rc=md,l=md+1;
else r=md-1;
}
return rc;
}
inline ll _len(int l, int r) {
if (d[l]>d[r]) swap(l,r); return d[r]-d[f[l]];
}
void _mdf(int &x,int l,int r,int _l,int _r,int tm) {
if (v[x].tm!=tm) { v[++cnt]=v[x],x=cnt,v[x].tm=tm;}
if (_l<=l&&r<=_r) ++v[x].tg;
else { int md=(l+r)>>1;
v[x].sm+=_len(bd[_l],bd[_r]);
if (_r<=md) _mdf(v[x].l,l,md,_l,_r,tm);
else if (_l>md) _mdf(v[x].r,md+1,r,_l,_r,tm);
else _mdf(v[x].l,l,md,_l,md,tm), _mdf(v[x].r,md+1,r,md+1,_r,tm);
}
}
void _qry(int &x,int l,int r,int _l,int _r,ll gt) {
gt+=v[x].tg;
if (_l<=l&&r<=_r) hv-=2ll*(v[x].sm+gt*_len(bd[l],bd[r]));
else { int md=(l+r)>>1;
if (_l<=md) _qry(v[x].l,l,md,_l,_r,gt);
if (_r>md) _qry(v[x].r,md+1,r,_l,_r,gt);
}
}
inline void modify(int x,int tm) {
int fx=b[x]; while (fx!=1) {
_mdf(rt[tm],1,n,dn[fx],dn[x],tm);
x=f[fx],fx=b[x];
}
if (x!=1) _mdf(rt[tm],1,n,dn[1],dn[x],tm);
}
inline ll query(int x,int tm) {
hv=1ll*tm*d[x]+sm[tm];
int fx=b[x]; while (fx!=1) {
_qry(rt[tm],1,n,dn[fx],dn[x],0);
x=f[fx],fx=b[x];
}
if (x!=1) _qry(rt[tm],1,n,dn[1],dn[x],0);
return hv;
}
int main() {
in(n),in(Q),in(A);
rep(i,1,n) in(hsh[i]),od[i]=i;
sort(od+1,od+1+n,cmp);
int a,b,c;
rep(i,1,n-1) in(a),in(b),in(c),add(a,b,c),add(b,a,c);
dfs(1), dfs(1,1);
rep(i,1,n) { rt[i]=rt[i-1],modify(od[i],i),sm[i]=sm[i-1]+d[od[i]]; }
xep(I,Q) {
in(c),in(a),in(b);
a=(a+as)%A, b=(b+as)%A; if(a>b) swap(a,b);
as=query(c,fd(b))-query(c,fd(a-1));
printf("%lld\n",as);
}
return 0;
}

留言