点分树

然后终于学了点分树,非常妙的说。

终于写完了Starria在好久之前写的紫荆花之恋(

看起来也不是很难写

然后就滚来写题解辣。

(突然发现这篇博客没写完就gg了 。。填坑)

对于一棵树我们不断求子树的重心,然后就强行得到了一个高度为log的点分树。

我们可以利用点分树的高度来保证一些奇怪的操作的复杂度。

点分治本身可以统计树上所有路径(点对?)的信息。

支持单点修改(?

大概就是直接算一下对每个父亲的贡献。

正常操作是每个父亲套一个数据结构。

感受一下紫荆花之恋

由于有加入操作我们暴力重构就可以了。

类似替罪羊树。

Starria内层写了替罪羊然后我也写了替罪羊
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
#include<bits/stdc++.h>
#define LL long long
#define N 100010
#define nlog 4000010
#define neww() stak[tp--]
inline LL read(){
char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar();
LL k=0,kk=1;if (c=='-')c=getchar(),kk=-1;
while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();return kk*k;
}using namespace std;
void write(LL x){if (x<0)x=-x,putchar('-');if (x/10)write(x/10);putchar(x%10+'0');}
void writeln(LL x){write(x);puts("");}
int fh[N][21],stak[nlog],tp,num[nlog],ll[nlog],rr[nlog],sum[nlog],n,x,y,ff[N],ffa[N],a[N*2][3],last[N];
int qwq[N],dee[N],z[N],dd,faq[nlog],mx[N],flag[N],d[N],tim,nn,ddd,f[N],g[N],stk[N],kk;
LL ans,kkkkk;
int lca(int x,int y){
if (qwq[x]<qwq[y])swap(x,y);
for (int i=20;i>=0;i--)if (qwq[fh[x][i]]>=qwq[y])x=fh[x][i];
for (int i=20;i>=0;i--)if (fh[x][i]!=fh[y][i])x=fh[x][i],y=fh[y][i];
return x==y?x:fh[x][0];
}void init(int x){
if (!x)return;stak[++tp]=x;z[++dd]=num[x];faq[x]=0;
if (ll[x])init(ll[x]);if (rr[x])init(rr[x]);ll[x]=0;rr[x]=0;
}void build233(int l,int r,int x){//平衡树重构
int mid=(l+r)>>1;num[x]=z[mid];faq[x]=1;
if (l<mid)ll[x]=neww(),build233(l,mid-1,ll[x]);else ll[x]=0;
if (mid<r)rr[x]=neww(),build233(mid+1,r,rr[x]);else rr[x]=0;
sum[x]=sum[ll[x]]+sum[rr[x]]+1;
}int find(int x,int y){
if (!x)return 0;
if (num[x]<=y)return sum[ll[x]]+1+find(rr[x],y);
else return find(ll[x],y);
}void put(int x,int y){
if (!faq[x]){faq[x]=sum[x]=1;num[x]=y;return;}
if (y<=num[x]){if (!ll[x])ll[x]=neww();put(ll[x],y);}
else {if (!rr[x])rr[x]=neww();put(rr[x],y);}
sum[x]=sum[ll[x]]+sum[rr[x]]+1;
if (max(sum[ll[x]],sum[rr[x]])*5>sum[x]*4){
z[dd=1]=num[x];if (ll[x])init(ll[x]);if (rr[x])init(rr[x]);
sort(z+1,z+1+dd);build233(1,dd,x);
}
}void dfs(int x,int fa){
mx[x]=0;d[x]=1;if (f[x])init(f[x]),f[x]=dd=0;if (g[x])init(g[x]),g[x]=dd=0;
for (int i=last[x];i;i=a[i][0])if (a[i][1]!=fa&&flag[a[i][1]]!=tim){
dfs(a[i][1],x);d[x]+=d[a[i][1]];mx[x]=max(mx[x],d[a[i][1]]);
}mx[x]=max(mx[x],nn-d[x]);if (mx[ddd]>mx[x])ddd=x;
}void ddfs1(int x,int fa,int de){
z[++dd]=de-ff[x];for (int i=last[x];i;i=a[i][0])
if (a[i][1]!=fa&&flag[a[i][1]]!=tim)ddfs1(a[i][1],x,de+a[i][2]);
}void ddfs2(int x,int fa,int de){
if (ffa[ddd])z[++dd]=dee[x]+dee[ffa[ddd]]-dee[lca(x,ffa[ddd])]*2-ff[x];
for (int i=last[x];i;i=a[i][0])
if (a[i][1]!=fa&&flag[a[i][1]]!=tim)ddfs2(a[i][1],x,de+a[i][2]);
}void build(int x,int fa){
nn=d[x];ddd=0;dfs(x,0);dfs(ddd,0);ffa[ddd]=fa;
int zx=ddd;flag[zx]=tim;f[zx]=neww();g[zx]=neww();
dd=0;ddfs1(zx,0,0);sort(z+1,z+1+dd);build233(1,dd,f[zx]);
dd=0;ddfs2(zx,0,0);sort(z+1,z+1+dd);if (dd)build233(1,dd,g[zx]);
for (int i=last[zx];i;i=a[i][0])
if (flag[a[i][1]]!=tim)build(a[i][1],zx);
}void calc(int x,int y){
int i=ffa[x],k=0;
while (i){
int dd=dee[x]+dee[i]-dee[lca(x,i)]*2;
ans+=find(f[i],y-dd);
if (k)ans-=find(k,y-dd);k=g[i];
i=ffa[i];
}
}void putit(int x){
int ddd=0;for (int i=x;i;i=ffa[i])stk[++ddd]=i;
for (int i=1;i<=ddd;i++){
if (!f[stk[i]])f[stk[i]]=neww();if (!g[stk[i]])g[stk[i]]=neww();
int dd=dee[x]+dee[stk[i]]-dee[lca(x,stk[i])]*2;
put(f[stk[i]],dd-ff[x]);if(i>1)put(g[stk[i-1]],dd-ff[x]);
d[stk[i]]++;mx[stk[i]]=max(mx[stk[i]],d[stk[i-1]]);
}stk[ddd+1]=0;tim++;
for (int i=ddd;i>=2;i--)if (mx[stk[i]]*5>d[stk[i]]*4){build(stk[i],stk[i+1]);return;}else flag[stk[i]]=tim;
}void add(int x,int y,int z){a[++kk][0]=last[x];a[kk][1]=y;a[kk][2]=z;last[x]=kk;}
signed main(){
for (int i=1;i<=4000000;i++)stak[++tp]=i;mx[0]=1e9;
read();n=read();for (int l=1;l<=n;l++){
x=read()^(ans%1000000000);
y=read();ff[l]=read();
if (x)add(l,x,y),add(x,l,y);fh[l][0]=ffa[l]=x;
qwq[l]=qwq[x]+1;dee[l]=dee[x]+y;
for (int i=1;i<=20;i++)fh[l][i]=fh[fh[l][i-1]][i-1];
calc(l,ff[l]);putit(l);writeln(ans);
}
}
分享到