Description

风见幽香有一个好朋友叫八云紫,她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动,打算在幻想乡开一家小店来做生意赚点钱。

这样的想法当然非常好啦,但是她们也发现她们面临着一个问题,那就是店开在哪里,面向什么样的人群。很神奇的是,幻想乡的地图是一个树形结构,幻想乡一共有 $n$个地方,编号为 $1$ 到 $n$,被 $n-1$ 条带权的边连接起来。每个地方都住着一个妖怪,其中第 $i$ 个地方的妖怪年龄是 $x_i$。

妖怪都是些比较喜欢安静的家伙,所以它们并不希望和很多妖怪相邻。所以这个树所有顶点的度数都小于或等于 $3$。妖怪和人一样,兴趣点随着年龄的变化自然就会变化,比如我们的 18 岁少女幽香和八云紫就比较喜欢可爱的东西。幽香通过研究发现,基本上妖怪的兴趣只跟年龄有关,所以幽香打算选择一个地方 $u$($u$为编号),然后在 $u$开一家面向年龄在 $L$到$R$ 之间(即年龄大于等于 $L$、小于等于 $R$)的妖怪的店。

也有可能 $u$这个地方离这些妖怪比较远,于是幽香就想要知道所有年龄在 $L$ 到 $R$ 之间的妖怪,到点 $u$ 的距离的和是多少(妖怪到 $u$ 的距离是该妖怪所在地方到 $u$ 的路径上的边的权之和) ,幽香把这个称为这个开店方案的方便值。

幽香她们还没有决定要把店开在哪里,八云紫倒是准备了很多方案,于是幽香想要知道,对于每个方案,方便值是多少呢。

Input

第一行三个用空格分开的数 $n,Q,A(n \le 150000, Q \le 200000)$,表示树的大小、开店的方案个数和妖怪的年龄上限。 第二行n个用空格分开的数 $x_1、x_2、…、x_n,x_i$ 表示第i 个地点妖怪的年龄,满足$0 \le x_i<A$。(年龄是可以为 $0$的,例如刚出生的妖怪的年龄为 $0$。) 接下来 $n-1$ 行,每行三个用空格分开的数 $a、b、c$,表示树上的顶点 $a$ 和 $b$ 之间有一条权为$c(1 \le c \le 1000)$的边,$a$和$b$ 是顶点编号。 接下来$Q$行,每行三个用空格分开的数 $u、 a、 b$。对于这 $Q$行的每一行,用 $a、b、A$计算出 $L$和$R$,表示询问”在地方 $u$开店,面向妖怪的年龄区间为$[L,R]$的方案的方便值是多少“。对于其中第 $1$ 行,$L$ 和 $R$ 的计算方法为:$L=\min(a \mod A , b \mod A ), R=\max(a \mod A,b \mod A)$。对于第 $2$到第 $Q$行,假设前一行得到的方便值为 $ans$,那么当前行的 $L$ 和 $R$ 计算方法为: $L=\min( (a+ans) \mod A, (b+ans) \mod A), $$R=\max((a+ans)\mod A,(b+ans)\mod A)$。

Output

对于每个方案,输出一行表示方便值。

Solution

听说这题是动态点分治?连点分治都没写过,然而用树剖也能很方便地解决。

考虑树上任意两点的距离$dis(u, v) = dep(u) + dep(v) - 2 * dep(lca)$($dep(u)$ 表示$u$到根的路径上的边权和),那么在这题中我们实际上要求的是一个区间内的点的与$u$的$lca$的$dep$之和。我们发现,如果对于这个区间内的每一个点,我们都将它到根的路径上的点的点权加上它们到它们父亲的边的权值,那么$dep(lca)$的和就是$u$到根的路径上的点权和。

这样我们就可以按年龄对点排序,用主席树在树链剖分的基础上维护点权和,就能算出答案了。要记录的信息比较多,注意要区别点的原编号和它的dfs序。

时空复杂度均为$O(nlog^2n)$,事实证明对树剖还是要有梦想的,一般区间不会太多,如果认真卡树剖就MLE了

Source

#include <cstdio>
#include <algorithm>
#include <vector>

#define For(i, j, k) for(int i = j; i <= k; i++)
#define pb push_back

const int N = 150010, Node = N * 100;

using namespace std;

typedef long long LL;

int n, m, Mod;

int age[N], num[N], suma[N], rootid[N], tot;
LL sumd[N], sumw[N], dis[N];
vector<int> G[N], wt[N], rk[N];

int top[N], fa[N], dep[N], faw[N], id[N], son[N], sz[N], dfn;

void DFS1(int h){
	sz[h] = 1;
	For(i, 0, (int)G[h].size() - 1){
		int v = G[h][i];
		if(v == fa[h]) continue;
		fa[v] = h, dis[v] = dis[h] + wt[h][i], faw[v] = wt[h][i];
		dep[v] = dep[h] + 1;
		DFS1(v);
		if(sz[v] > sz[son[h]]) son[h] = v;
		sz[h] += sz[v];
	}
}

void DFS2(int h){
	id[h] = ++dfn;
	sumw[dfn] = sumw[dfn - 1] + faw[h];
	top[h] = son[fa[h]] == h ? top[fa[h]] : h;
	if(son[h]) DFS2(son[h]);
	For(i, 0, (int)G[h].size() - 1){
		int v = G[h][i];
		if(v == fa[h] || v == son[h]) continue;
		DFS2(v);
	}
}

namespace PresidentTree{
	
	struct info{
		int lc, rc;
		LL sum, addv;
	}A[Node];
	
	int root[N << 4], node, nowroot;

	#define M ((L + R) >> 1)

	void add(int &o, int old, int L, int R, int l, int r){
		o = ++node;
		A[o] = A[old];
		if(l <= L && R <= r) A[o].addv++, A[o].sum += sumw[R] - sumw[L - 1];
		else{
			if(l <= M) add(A[o].lc, A[old].lc, L, M, l, r);
			if(r > M) add(A[o].rc, A[old].rc, M + 1, R, l, r);
			A[o].sum += sumw[min(R, r)] - sumw[max(l, L) - 1];
		}
	}

	LL query(int o, int L, int R, int l, int r, LL sumadd = 0){
		if(l <= L && R <= r) return sumadd * (sumw[R] - sumw[L - 1]) + A[o].sum;
		else{
			sumadd += A[o].addv;
			LL ret = 0;
			if(l <= M) ret += query(A[o].lc, L, M, l, r, sumadd);
			if(r > M) ret += query(A[o].rc, M + 1, R, l, r, sumadd);
			return ret;
		}
	}

};

using namespace PresidentTree;

void modify(int u){
	while(u){
		int x = top[u], t = root[nowroot];
		add(root[++nowroot], t, 1, n, id[x], id[u]);
		u = fa[x];
	}
}

LL calc(int u, int rt){
	LL ret = 0;
	while(u){
		int x = top[u];
		ret += query(rt, 1, n, id[x], id[u]);
		u = fa[x];
	}
	return ret;
}

int main(){
	scanf("%d%d%d", &n, &m, &Mod);

	For(i, 1, n) scanf("%d", &age[i]), num[++tot] = age[i];
	sort(num + 1, num + tot + 1), tot = (int)(unique(num + 1, num + tot + 1) - num) - 1;
	For(i, 1, n) age[i] = (int)(lower_bound(num + 1, num + tot + 1, age[i]) - num), rk[age[i]].pb(i);

	For(i, 2, n){
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		G[u].pb(v), G[v].pb(u);
		wt[u].pb(w), wt[v].pb(w);
	}
	DFS1(1), DFS2(1);

	For(i, 1, tot){
		sumd[i] = sumd[i - 1], suma[i] = suma[i - 1] + rk[i].size();
		For(j, 0, (int)rk[i].size() - 1) sumd[i] += dis[rk[i][j]], modify(rk[i][j]);
		rootid[i] = nowroot;
	}

	LL lstans = 0;
	For(i, 1, m){
		int u;
		LL a, b, x, y;
		scanf("%d%lld%lld", &u, &a, &b);
		x = (a + lstans) % Mod, y = (b + lstans) % Mod;
		a = min(x, y), b = max(x, y);
		a = lower_bound(num + 1, num + tot + 1, a) - num;
		b = upper_bound(num + 1, num + tot + 1, b) - num - 1;
		lstans = (suma[b] - suma[a - 1]) * dis[u] + (sumd[b] - sumd[a - 1]) 
			- 2 * (calc(u, root[rootid[b]]) - calc(u, root[rootid[a - 1]]));
		printf("%lld\n", lstans);
	}

	return 0;
}