Bzoj4012

, ,

点分树两个关键的性质：

  • 点分树最大深度是 $\log$ 级别的

  • 点分树上两点的 $lca$ 在原树上两点之间的路径上

Solution

前情提要：那个每个点的度数小于等于三是用来卡常的。

首先假设没有 $l,r$ 的限制，询问某个点到其他所有点的距离之和，我们用点分树去做该如何做。

$sum[x][0]$ 表示点分树上$x$子树的所有点到 $x$ 的距离和

$sum[x][1]$ 表示点分树上 $x$ 子树的所有点到 $x$ 点分树上父亲的距离和

$size_x$ 表示点分树上 $x$ 子树大小

显然对于询问的点 $x$，我们跳点分树上的父亲即可，初始时 $ans$ 设为也就 $sum[x][0]$ 是点分树 $x$ 子树下方的贡献和。

跳点分树父亲时，当前跳到点 $i$（点 $i$ 要有父亲），$ans += sum[fa_i][0] - sum[i][1] + (siz_{fa_i} - siz_i) * Dis(x, fa_i)$

其中的减法是减去多算的。

加上 $l,r$ 的限制，只要把每个节点的在点分树上子树的点全存在一个 $vector$ 里，排个序然后前缀和+二分即可。

解决路径相关而与树的形态不想关的题目，考虑点分治或者点分树。

code

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include<bits/stdc++.h>
#define ll long long 
#define maxn 200005
#define put() putchar('\n')
using namespace std;
struct FastIO{
	static const int S=1048576;
	char buf[S],*L,*R;int stk[20],Top;~FastIO(){clear();}
	inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
	inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}inline void endl(){pc('\n');}
	FastIO& operator >> (char&ch){while(ch=nc(),ch==' '||ch=='\n');return *this;}
	template<typename T>FastIO& operator >> (T&ret){
		ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
		while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;
	}
	FastIO& operator >> (char* s){int Len=0;char ch=nc();while(ch!='\n'){*(s+Len)=ch;Len++;ch=nc();}}
	template<typename T>FastIO& operator << (T x){
		if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);
		while(stk[0]) pc('0'+stk[stk[0]--]);return *this;
	}
	FastIO& operator << (char ch){pc(ch);return *this;}
	FastIO& operator << (string str){int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
const int inf=1e9;
int h[maxn],head=1,lg[maxn],n,m;
int w[maxn],fa[maxn],size[maxn],Max[maxn];
ll dis[maxn];
struct yyy{
	ll sum;int id;
	yyy(int a=0,ll b=0) {id=a;sum=b;}
	bool operator <(const yyy &x) const {return id<x.id;} 
};
vector<yyy>t[maxn][2];
bitset<maxn> vis;
struct node{
	int to,z,w;
	inline void add(int x,int y,int val){
		to=y;z=h[x];h[x]=head;w=val;
	}
}a[maxn*2];
namespace lca{
	int fa[maxn][21],deep[maxn];
	inline void dfs(int x,int pre){
		int i;deep[x]=deep[pre]+1;fa[x][0]=pre;
		for (i=1;i<=lg[deep[x]];i++) fa[x][i]=fa[fa[x][i-1]][i-1];
		for (i=h[x];i;i=a[i].z) if (a[i].to^pre) dis[a[i].to]=dis[x]+a[i].w,dfs(a[i].to,x);
	}
	inline int query(int x,int y){
		int i;
		if (deep[x]<deep[y]) swap(x,y);
		while (deep[x]>deep[y]) x=fa[x][lg[deep[x]-deep[y]]];
		if (x==y) return x;
		for (i=lg[deep[x]];i>=0;i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
		return fa[x][0];
	}
	inline ll d(int x,int y){
		return dis[x]+dis[y]-2*dis[query(x,y)];
	}
}
int root,Size,maxroot;
inline void dfs(int x,int pre){
	int i;size[x]=1;
//	t[root][0].push_back(yyy(w[x],lca::d(x,root)));
//	if (fa[root]) t[root][1].push_back(yyy(w[x],lca::d(x,fa[root])));
	for (i=h[x];i;i=a[i].z) 
	    if (a[i].to!=pre&&!vis[a[i].to]) 
		    dfs(a[i].to,x),size[x]+=size[a[i].to];
}
inline void getroot(int x,int pre) {
	int i,maxs=0;size[x]=1;
	for (i=h[x];i;i=a[i].z)
	    if (a[i].to!=pre&&!vis[a[i].to]) {
	    	getroot(a[i].to,x);
	        size[x]+=size[a[i].to];
	        maxs=max(maxs,size[a[i].to]);
		}
	maxs=max(maxs,Size-size[x]);
	if (maxroot>maxs) root=x,maxroot=maxs;
}
inline void solve(int x,int pre) {
	int i;
	vis[x]=1;dfs(x,0);
	for (i=h[x];i;i=a[i].z)
	    if (!vis[a[i].to]) {
	    	maxroot=inf;Size=size[a[i].to];getroot(a[i].to,x);
	    	fa[root]=x;solve(root,x);
		}
}
inline ll query(int op,int x,int l,int r,ll &size) {
	int lef=lower_bound(t[x][op].begin(),t[x][op].end(),yyy(l,0))-t[x][op].begin()-1;
	int rig=upper_bound(t[x][op].begin(),t[x][op].end(),yyy(r,0))-t[x][op].begin()-1;
	size=rig-lef;
	ll ans=0;
	if (rig>=0&&rig<t[x][op].size()) ans+=t[x][op][rig].sum;
	if (lef>=0&&lef<t[x][op].size()) ans-=t[x][op][lef].sum;
	return ans;
}
ll lastans;
signed main(){
    int i,x,y,z,j,A,len;
    int l,r;
    fin>>n>>m>>A;
    for (i=1;i<=n;i++) fin>>w[i];
    for (i=1;i<n;i++) {
    	fin>>x>>y>>z;
    	a[++head].add(x,y,z);
    	a[++head].add(y,x,z);
	}
	for (i=2;i<=n;i++) lg[i]=lg[i/2]+1;
	lca::dfs(1,0);
	Size=n;maxroot=inf;
	getroot(1,0);
	solve(root,0);
	for (i=1;i<=n;i++) {
		for (j=i;j;j=fa[j]) {
			t[j][0].push_back(yyy(w[i],lca::d(i,j)));
			if (fa[j]) t[j][1].push_back(yyy(w[i],lca::d(i,fa[j])));
		}
	}
	for (i=1;i<=n;i++) {
		sort(t[i][0].begin(),t[i][0].end());
		sort(t[i][1].begin(),t[i][1].end());
		len=t[i][0].size();for (j=1;j<len;j++) t[i][0][j].sum+=t[i][0][j-1].sum;
		len=t[i][1].size();for (j=1;j<len;j++) t[i][1][j].sum+=t[i][1][j-1].sum;
	}
	while (m--){
		fin>>x>>l>>r;
		l=(lastans+l)%A;r=(lastans+r)%A;
		if (l>r) swap(l,r);
		ll sum1=0,sum2=0;
		lastans=query(0,x,l,r,sum1);
		for (i=x;fa[i];i=fa[i]) {
			lastans+=query(0,fa[i],l,r,sum2)-query(1,i,l,r,sum1);
			lastans+=(sum2-sum1)*lca::d(x,fa[i]);
		}
		printf("%lld\n",lastans);
	}
    return 0;
}