[HNOI2015]开店 题解
![[HNOI2015]开店 题解](https://ksmeow.moe/wp-content/uploads/2018/07/180713b.jpg)
题目地址：洛谷：【P3241】[HNOI2015]开店 – 洛谷、BZOJ：Problem 4012. — [HNOI2015]开店
题目描述
风见幽香有一个好朋友叫八云紫，她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动，打算在幻想乡开一家小店来做生意赚点钱。这样的想法当然非常好啦，但是她们也发现她们面临着一个问题，那就是店开在哪里，面向什么样的人群。很神奇的是，幻想乡的地图是一个树形结构，幻想乡一共有 n个地方，编号为 1 到 n，被 n-1 条带权的边连接起来。每个地方都住着一个妖怪，其中第 i 个地方的妖怪年龄是 x_i。妖怪都是些比较喜欢安静的家伙，所以它们并不希望和很多妖怪相邻。所以这个树所有顶点的度数都小于或等于 3。妖怪和人一样，兴趣点随着年龄的变化自然就会变化，比如我们的 18 岁少女幽香和八云紫就比较喜欢可爱的东西。幽香通过研究发现，基本上妖怪的兴趣只跟年龄有关，所以幽香打算选择一个地方 u（u为编号），然后在 u开一家面向年龄在 L到R 之间（即年龄大于等于 L、小于等于 R）的妖怪的店。也有可能 u这个地方离这些妖怪比较远，于是幽香就想要知道所有年龄在 L 到 R 之间的妖怪，到点 u 的距离的和是多少（妖怪到 u 的距离是该妖怪所在地方到 u 的路径上的边的权之和），幽香把这个称为这个开店方案的方便值。幽香她们还没有决定要把店开在哪里，八云紫倒是准备了很多方案，于是幽香想要知道，对于每个方案，方便值是多少呢。
题意简述
给你一棵$n$个点的二叉树，每个点有点权，每条边有边权，有$Q$个询问，每次询问树上所有点权在$[L, R]$范围内的点到$u$的距离之和，强制在线。
输入输出格式
输入格式：
第一行三个用空格分开的数 n、Q和A，表示树的大小、开店的方案个数和妖怪的年龄上限。
第二行n个用空格分开的数 x_1、x_2、…、x_n，x_i 表示第i 个地点妖怪的年龄，满足0<=x_i<A。(年龄是可以为 0的，例如刚出生的妖怪的年龄为 0。)
接下来 n-1 行，每行三个用空格分开的数 a、b、c，表示树上的顶点 a 和 b 之间有一条权为c(1 <= c <= 1000)的边，a和b 是顶点编号。
接下来Q行，每行三个用空格分开的数 u、 a、 b。对于这 Q行的每一行，用 a、b、A计算出 L和R，表示询问“在地方 u开店，面向妖怪的年龄区间为[L,R]的方案的方便值是多少”。对于其中第 1 行，L 和 R 的计算方法为：L=min(a%A,b%A), R=max(a%A,b%A)。对于第 2到第 Q行，假设前一行得到的方便值为 ans，那么当
前行的 L 和 R 计算方法为： L=min((a+ans)%A,(b+ans)%A), R=max((a+ans)%A,(b+ans)%A)。
输出格式：
对于每个方案，输出一行表示方便值。
输入输出样例
输入样例#1：
10 10 10 0 0 7 2 1 4 7 7 7 9 1 2 270 2 3 217 1 4 326 2 5 361 4 6 116 3 7 38 1 8 800 6 9 210 7 10 278 8 9 8 2 8 0 9 3 1 8 0 8 4 2 7 9 7 3 4 7 0 2 2 7 3 2 1 2 3 4
输出样例#1：
1603 957 7161 9466 3232 5223 1879 1669 1282 0
说明
满足 n<=150000,Q<=200000。对于所有数据，满足 A<=10^9
题解
我们使用边分治解决这个问题，因为树是二叉树，具有很优秀的性质，适合使用边分治。我们考虑在分治过程中记录下子分治结构所有点到中心边两端点的距离的集合，并以此计算权值下标的距离前缀和。我们将分治树的树形态保存下来，对于每个点显然对应着分治树的一个树链，对于树链上的每一个中心边，求出询问点对侧半棵树点权在区间内的点的距离之和，可以利用二分查找和之前的前缀和求出，这些点对答案的贡献=距离之和+点数*(中心边边权+询问点到该侧中心边端点的距离)。
简单地说就是用一个边分树优化了暴力查找的过程，使得查找涉及的点规模降至$O(\log n)$，因此每次查找的复杂度是$O(\log^2 n)$的，即总复杂度为$O(n \log^2 n)$。虽然这个复杂度与树链剖分是一致的，但是常数比树剖不知道大到哪去了，因此在洛谷上得开O2过，而且由于维护的信息多，相对空间占用也比树剖大。
以及，如果随机小数据没卵问题，随机大数据小概率出问题，那大概可能是因为维护信息用了个set，而set会去重，要改成multiset QAQ
代码
// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1; register char c = fgc();
for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
return res * neg;
}
const int MAXN = 150005;
int n, q;
LL A, w[MAXN];
struct Edge {
int to;
LL w;
int nxt;
} gra[MAXN << 1];
int head[MAXN], tot;
inline void addedge(int u, int v, LL w) {
gra[tot] = Edge {v, w, head[u]}; head[u] = tot++;
gra[tot] = Edge {u, w, head[v]}; head[v] = tot++;
}
bool del[MAXN];
int siz[MAXN], ct, ctsiz;
void dfs_size(int u, int fa) {
siz[u] = 1;
for(int i = head[u]; ~i; i = gra[i].nxt) {
int v = gra[i].to;
if(v == fa || del[i >> 1]) continue;
dfs_size(v, u);
siz[u] += siz[v];
}
}
void findct(int u, int fa, int tot) {
for(int i = head[u]; ~i; i = gra[i].nxt) {
int v = gra[i].to;
if(v == fa || del[i >> 1]) continue;
findct(v, u, tot);
int vsiz = std::max(siz[v], tot - siz[v]);
if(vsiz < ctsiz) {
ct = i; ctsiz = vsiz;
}
}
}
struct Info {
LL did, s, dis;
};
struct Info2 {
LL w, dis, cnt;
inline bool operator<(const Info2 &rhs) const {
return w < rhs.w;
}
inline bool operator<=(const Info2 &rhs) const {
return w <= rhs.w;
}
inline bool operator>(const Info2 &rhs) const {
return w > rhs.w;
}
inline bool operator>=(const Info2 &rhs) const {
return w >= rhs.w;
}
};
std::vector<Info> pinfo[MAXN];
typedef std::pair<LL, LL> PII;
std::priority_queue<PII, std::vector<PII>, std::greater<PII> > cinfom;
std::vector<Info2> cinfo[MAXN][2];
int eid[MAXN], ctot;
void dfs_dis(int u, int fa, LL dis, int did, int s) {
cinfom.push(PII(w[u], dis));
pinfo[u].push_back(Info {did, s, dis});
for(int i = head[u]; ~i; i = gra[i].nxt) {
int v = gra[i].to;
if(v == fa || del[i >> 1]) continue;
dfs_dis(v, u, dis + gra[i].w, did, s);
}
}
inline void work(int u, int s, int did) {
dfs_dis(u, 0, 0, did, s);
LL lst = -1, lid = 0;
cinfo[did][s].push_back(Info2 {-1, 0, 0});
while(!cinfom.empty()) {
if(cinfom.top().first != lst) {
cinfo[did][s].push_back(Info2 {cinfom.top().first, 0, 0});
lst = cinfom.top().first; lid++;
}
cinfo[did][s][lid].dis += cinfom.top().second;
cinfo[did][s][lid].cnt++;
cinfom.pop();
}
for(int i = 1; i < cinfo[did][s].size(); i++) {
cinfo[did][s][i].dis += cinfo[did][s][i - 1].dis;
cinfo[did][s][i].cnt += cinfo[did][s][i - 1].cnt;
}
}
void divide(int u) {
dfs_size(u, 0);
ct = -1; ctsiz = n; findct(u, 0, siz[u]);
if(ct == -1) return;
int x = gra[ct].to, y = gra[ct ^ 1].to, t = ++ctot;
del[ct >> 1] = true;
work(x, 0, t); work(y, 1, t);
eid[t] = ct;
divide(x); divide(y);
}
inline LL query(int u, LL l, LL r) {
LL res = 0;
for(int i = 0; i < pinfo[u].size(); i++) {
Info info = pinfo[u][i];
int s = info.s;
std::vector<Info2>::iterator
lit = std::lower_bound(cinfo[info.did][s ^ 1].begin(), cinfo[info.did][s ^ 1].end(), Info2 {l, 0, 0}) - 1,
rit = std::upper_bound(cinfo[info.did][s ^ 1].begin(), cinfo[info.did][s ^ 1].end(), Info2 {r, 0, 0}) - 1;
LL dis = rit->dis - lit->dis, cnt = rit->cnt - lit->cnt;
res += dis + 1ll * cnt * (gra[eid[info.did]].w + info.dis);
}
return res;
}
int main() {
memset(head, -1, sizeof(head));
n = readint(); q = readint(); A = readint();
for(int i = 1; i <= n; i++) {
w[i] = readint();
}
for(int i = 1, a, b, c; i < n; i++) {
a = readint(); b = readint(); c = readint();
addedge(a, b, c);
}
divide(1);
LL lastans = 0;
while(q--) {
LL u = readint(), a = readint(), b = readint(),
l = std::min((a + lastans) % A, (b + lastans) % A),
r = std::max((a + lastans) % A, (b + lastans) % A);
printf("%lld\n", lastans = query(u, l, r));
}
return 0;
}
