「HNOI2015」开店(树链剖分，主席树）

/*

考虑将所求的值拆分

记每个点到根的路径长度为dis_i， 那么我们要求的就是\sum_{i = l} ^ r dis_i + dis[u] * (r - l + 1)

- 2\sum_{i = l} ^ r dis_{LCA(i, u)}

前两个前缀和处理

对于第三个可以转换成一个经典问题， 就是对于每个点到根的路径  + 1, 那么第三个东西就是这个点到根的贡献和了 

*/

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#include<iostream>

#define ll long long

#define mmp make_pair

#define M 200010

using namespace std;

int read()

{

	int nm = 0, f = 1;

	char c = getchar();

	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;

	for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';

	return nm * f;

}

int n, q, A, sz[M], son[M], fa[M], top[M], dfn[M], dft, ver[M], cnt;

ll dis[M], ans, sum[M], w[M];

pair<int, int> sta[M];

vector<pair<int, int> > to[M];

int lc[10001000], rc[10001000], v[10001000], rt[M];

ll t[10001000];

void dfs(int now, int f)

{

	sz[now] = 1;

	fa[now] = f;

	for(int i = 0; i < to[now].size(); i++)

	{

		int vj = to[now][i].first, v = to[now][i].second;

		if(vj == f) continue;

		dis[vj] = dis[now] + v;

		ver[vj] = v;

		dfs(vj, now);

		if(sz[vj] > sz[son[now]]) son[now] = vj;

		sz[now] += sz[vj];

	}

}

void dfs(int now)

{

	dfn[now] = ++dft;

	w[dfn[now]] = ver[now];

	if(son[now])

	{

		top[son[now]] = top[now];

		dfs(son[now]);

	}

	for(int i = 0; i < to[now].size(); i++)

	{

		int vj = to[now][i].first;

		if(vj == fa[now] || vj == son[now]) continue;

		top[vj] = vj;

		dfs(vj);

	}

}

void modify(int last, int &now, int l, int r, int ln, int rn)

{

	now = ++cnt;

	lc[now] = lc[last], rc[now] = rc[last], t[now] = t[last], v[now] = v[last];

	if(l == ln && r == rn)

	{

		v[now]++;

		return;

	}

	t[now] += w[rn] - w[ln - 1];

	int mid = (l + r) >> 1;

	if(ln > mid) modify(rc[last], rc[now], mid + 1, r, ln, rn);

	else if(rn <= mid) modify(lc[last], lc[now], l, mid, ln, rn);

	else modify(lc[last], lc[now], l, mid, ln, mid), modify(rc[last], rc[now], mid + 1, r, mid + 1, rn);

}

ll query(int now, int l, int r, int ln, int rn)

{

	ll ans = 1ll * (w[rn] - w[ln - 1]) * v[now];

	if(l == ln && r <= rn) return ans + t[now];

	int mid = (l + r) >> 1;

	if(rn <= mid) return ans + query(lc[now], l, mid, ln, rn);

	else if(ln > mid) return ans + query(rc[now], mid + 1, r, ln, rn);

	else return ans + query(lc[now], l, mid, ln, mid) + query(rc[now], mid + 1, r, mid + 1, rn);

}

void Modify(int &now, int x)

{

	for(; top[x] != 1; x = fa[top[x]]) modify(now, now, 1, n, dfn[top[x]], dfn[x]);

	modify(now, now, 1, n, dfn[1], dfn[x]);

}

ll Query(int now, int x)

{

	ll ans = 0;

	for(; top[x] != 1; x = fa[top[x]]) ans += query(now, 1, n, dfn[top[x]], dfn[x]);

	ans += query(now, 1, n, dfn[1], dfn[x]);

	return ans;

}

int main()

{

	n = read(), q = read(), A = read();

	for(int i = 1; i <= n; i++) sta[i] = mmp(read(), i);

	sort(sta + 1, sta + n + 1);

	for(int i = 1; i < n; i++)

	{

		int vi = read(), vj = read(), v = read();

		to[vi].push_back(mmp(vj, v));

		to[vj].push_back(mmp(vi, v));

	}

	dfs(1, 0);

	top[1] = 1;

	dfs(1);

	for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + dis[sta[i].second], w[i] += w[i - 1];

	for(int i = 1; i <= n; i++) rt[i] = rt[i - 1], Modify(rt[i], sta[i].second);

	while(q--)

	{

		int u = read(), l = read(), r = read();

		l = (ans + l) % A, r = (ans + r) % A;

		if(r < l) swap(l, r);

		ans = 0;

		l = lower_bound(sta + 1, sta + n + 1, mmp(l, 0)) - sta,

		r = lower_bound(sta + 1, sta + n + 1, mmp(r, 0x3e3e3e3e)) - sta - 1;

		ans += Query(rt[l - 1], u);

		ans -= Query(rt[r], u);

		ans *= 2;

		ans += 1ll * (r - l + 1) * dis[u];

		ans += sum[r] - sum[l - 1];

		cout << ans << "\n";

	}

	return 0;

}
巴特西

「HNOI2015」开店(树链剖分，主席树）

最新文章

热门文章

巴特西

「HNOI2015」开店(树链剖分， 主席树）

最新文章

热门文章

「HNOI2015」开店(树链剖分，主席树）
