一时兴起在博客里搜索『点分治』，发现没有匹配项。
定义
适用于解决和点对、路径相关的问题。
对于任意点 \(x\)，树上任意简单路径 \((u,v)\) 被分为几类：
- 不经过 \(x\)。
- 经过 \(x\)：
- 一个端点为 \(x\)。
- 两个端点都不为 \(x\)：可以由上一种情况拼接得到。
如果我们把每个点作为 \(x\) 的情况都枚举一遍，再统计不重复的 \((u,v)\)，在一种特定的枚举顺序下可以做到 \(O(n\log n)\) 完成所有点对的枚举。
证明略，每次取子树重心，只遍历没遍历过的点即可。
关于子树重心，一则阅读材料：一种基于错误的寻找重心方法的点分治的复杂度分析。
CF1575E Eye-Pleasing City Park Tour
https://codeforces.com/problemset/problem/1575/E
随便用线段树维护一下就行了。复杂度 \(O(n\log^2 n)\)。
随便维护一下 
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, k;
std::cin >> n >> k;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
std::vector<std::vector<std::pair<int, int> > > g(n + 1);
for (int i = 1, x, y, c; i < n; ++i) {
std::cin >> x >> y >> c;
g[x].emplace_back(y, c), g[y].emplace_back(x, c);
}
std::vector<std::vector<std::pair<int, long long> > > bit(2, std::vector<std::pair<int, long long> > (n + 1));
auto lowbit = [&](int x) {
return x & -x;
};
auto add = [&](int id, int x, long long v, int type) {
for (++x; x <= n; x += lowbit(x))
bit[id][x].first += type, (bit[id][x].second += v * type) %= mod;
return;
};
auto ask = [&](int id, int x) {
std::pair<int, long long> res;
for (++x; x; x -= lowbit(x))
res.first += bit[id][x].first, (res.second += bit[id][x].second) %= mod;
return res;
};
std::vector<int> p, siz(n + 1), mx(n + 1), tag(n + 1);
std::function<void(int, int)> findp = [&](int x, int fa) {
p.push_back(x);
siz[x] = 1, mx[x] = 0;
for (auto [i, c] : g[x])
if (i != fa && !tag[i]) {
findp(i, x);
siz[x] += siz[i];
mx[x] = std::max(mx[x], siz[i]);
}
return;
};
auto findrt = [&](int x) {
std::vector<int>().swap(p), findp(x, -1);
int n = (int)p.size();
for (auto i : p)
if (mx[i] <= n / 2 && n - siz[i] <= n / 2)
return i;
return -1;
};
auto res(0ll);
std::function<void(int, int, int, int, int, long long, int, int)> calc = [&](int x, int fa, int oc, int la, int cnt, long long s, int os, int type) {
if (cnt > k)
return;
if (type == 0) {
auto t0(ask(oc, k - cnt)), t1(ask(!oc, k - cnt - 1));
// auto lr(res);
(res += t0.first * (s - os) + t0.second) %= mod;
(res += t1.first * (s - os) + t1.second) %= mod;
// printf(" %d(%d, %lld): ask[0](%d) = (%d, %lld), ask[1](%d) = (%d, %lld), res += %lld\n", x, cnt, s - os, k - cnt, t0.first, t0.second, k - cnt - 1, t1.first, t1.second, res - lr);
}
else if (type != 0) {
// printf(" %d(%d, %lld): add(%d, %lld)\n", x, cnt, s - os, oc, s * type);
add(oc, cnt, s, type);
}
for (auto [i, c] : g[x])
if (i != fa && !tag[i])
calc(i, x, oc, c, cnt + (la != c), (s + a[i]) % mod, os, type);
return;
};
std::function<void(int)> DFS = [&](int x) {
x = findrt(x);
// printf("DFS %d\n", x);
for (auto [i, c] : g[x])
if (!tag[i]) {
calc(i, x, c, c, 0, (a[x] + a[i]) % mod, a[x], 0);
calc(i, x, c, c, 0, (a[x] + a[i]) % mod, a[x], 1);
}
(res += ask(0, k).second + ask(1, k).second) %= mod;
(res += a[x]) %= mod;
// printf("res += %lld + %lld\n", ask(0, k).second, ask(1, k).second);
for (auto [i, c] : g[x])
if (!tag[i])
calc(i, x, c, c, 0, (a[x] + a[i]) % mod, a[x], -1);
// assert(!ask(0, k).second);
tag[x] = 1;
for (auto [i, c] : g[x])
if (!tag[i])
DFS(i);
return;
};
DFS(1);
std::cout << (res + mod) % mod << '\n';
return 0;
}A - 三元图 Graf
https://www.luogu.com.cn/problem/P10829
发现很圆方树；观察题图，肯定想要把中间的方点作为树根。
发现它就是重心；进一步地，整个圆方树其实是一个点分治的结构。显然除了最后一层，每次找到的重心都应该是方点；并且其应该有三个等大的儿子。check 上述两点即可。
唉还是挺常规的，限制我做出来这道题的应该是我已经 > 1y 没写过连通性问题了 😅
怎么还有人不会判重边的 😅
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int> > g(n + 1), _g(n + 1);
auto nosol = [](void) {
std::cout << "ne" << '\n';
exit(0);
return;
};
std::set<std::pair<int, int> > t;
for (int x, y; m--; ) {
std::cin >> x >> y;
if (x == y || t.count({ x, y }))
nosol();
t.insert({ x, y }), t.insert({ y, x });
_g[x].push_back(y), _g[y].push_back(x);
}
std::vector<int> st, dfn(n + 1), low(n + 1);
std::function<void(int, int)> DFS = [&](int x, int fa) {
static int now = 0;
st.push_back(x);
dfn[x] = low[x] = ++now;
for (auto i : _g[x])
if (!dfn[i]) {
DFS(i, x);
low[x] = std::min(low[x], low[i]);
if (low[i] >= dfn[x]) {
++n, g.emplace_back();
for (int p = st.back(); ; p = st.back()) {
g[n].push_back(p), g[p].push_back(n);
st.pop_back();
if (p == i)
break;
}
g[n].push_back(x), g[x].push_back(n);
}
}
else if (i != fa)
low[x] = std::min(low[x], dfn[i]);
return;
};
int n1 = n;
DFS(1, -1);
std::vector<int> siz(n + 1), p, mx(n + 1), tag(n + 1);
DFS = [&](int x, int fa) {
siz[x] = 1, mx[x] = 0;
p.push_back(x);
for (auto i : g[x])
if (i != fa && !tag[i]) {
DFS(i, x);
siz[x] += siz[i];
mx[x] = std::max(mx[x], siz[i]);
}
return;
};
auto findrt = [&](int x) {
p.clear(), DFS(x, -1);
int n = (int)p.size();
for (auto i : p)
if (mx[i] <= n / 2 && n - siz[i] <= n / 2)
return i;
return -1;
};
std::function<void(int)> DFS1 = [&](int x) {
x = findrt(x), DFS(x, -1);
int si = -1, cnt = 0;
if (siz[x] == 1) {
if (x > n1)
nosol();
return;
}
if (x <= n1)
nosol();
for (auto i : g[x])
if (!tag[i]) {
++cnt;
if (~si && si != siz[i])
nosol();
if (si == -1)
si = siz[i];
}
if (cnt != 3)
nosol();
tag[x] = 1;
for (auto i : g[x])
if (!tag[i])
DFS1(i);
return;
};
DFS1(1);
std::cout << "da" << '\n';
return 0;
}B - Distance on Triangulation
https://www.luogu.com.cn/problem/P6976
众（除了我）所周知 凸多边形的三角剖分可以转化为树上问题，故把树建出来；一个重要的点是要认识到这个树的意义。树上的点其实是没什么物理含义的；经过了某一个树上的点和经过了三角形上的任一点是等价的；也就是说，想要从某个点走到另一个点，肯定要经过对应的树上路径，但这不能反应实际距离什么的，只是能获取路径可能包含的点和必须包含的点（的超集），具体还是要最短路。
接着转化为点分治。但其实这里的点分治有点像序列分治：先跑一遍根节点（三个）在当前分治范围内的最短路，然后处理经过了这个点的询问，然后递归。容易发现三个点里有一些之前被算过了，且一定包含了这个分治范围，直接跳过就行了。
注意询问要写成整体二分那种动态下传的形式，只把被某个子树完全包含的询问传下去；不然复杂度是错的。以及这样就可以剪枝：发现询问数组空了就可以停了。直接 TLE to 200ms 了 😅
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
std::vector<int> deg(n + 1);
std::vector<std::vector<int> > _g(n + 1), g(n + 1);
for (int i = 1; i < n; ++i) {
_g[i].push_back(i + 1), _g[i + 1].push_back(i);
++deg[i], ++deg[i + 1];
}
_g[1].push_back(n), _g[n].push_back(1);
++deg[1], ++deg[n];
for (int i = 1, x, y; i <= n - 3; ++i) {
std::cin >> x >> y;
_g[x].push_back(y), _g[y].push_back(x);
++deg[x], ++deg[y];
}
int cnt = 0;
std::vector<std::vector<int> > t(1);
{
std::queue<int> q;
std::vector<int> inq(n + 1);
for (int i = 1; i <= n; ++i)
if (deg[i] == 2)
q.push(i);
std::map<std::pair<int, int>, int> st;
for (; !q.empty(); ) {
int x = q.front();
q.pop(), inq[x] = 1;
if (deg[x] == 2) {
++cnt, t.push_back({ x });
for (auto i : _g[x])
if (!inq[i]) {
t[cnt].push_back(i);
}
std::sort(t[cnt].begin(), t[cnt].end());
for (int a = 0; a < 2; ++a)
for (int b = a + 1; b < 3; ++b) {
std::pair<int, int> now(t[cnt][a], t[cnt][b]);
if (st.count(now)) {
int to = st[now];
// printf("add %d <-> %d\n", to, cnt);
g[cnt].push_back(to), g[to].push_back(cnt);
}
else
st[now] = cnt;
}
}
for (auto i : _g[x])
if (--deg[i] == 2)
q.push(i);
}
}
int q;
std::cin >> q;
std::vector<int> res(q + 1, 0x3f3f3f3f);
std::vector<std::tuple<int, int, int> > u(q);
for (int i = 1, x, y; i <= q; ++i)
std::cin >> x >> y, u[i - 1] = { x, y, i };
int tik = 0;
std::vector<int> siz(cnt + 1), mx(cnt + 1), p, now(n + 1), p1;
std::vector<int> dis(n + 1), tag(n + 1), vis(n + 1), faa(n + 1);
std::function<void(int, int)> DFS1 = [&](int x, int fa) {
siz[x] = 1, mx[x] = 0;
p.push_back(x);
for (auto i : t[x])
now[i] = tik, p1.push_back(i);
for (auto i : g[x])
if (i != fa && !tag[i]) {
DFS1(i, x);
siz[x] += siz[i];
mx[x] = std::max(mx[x], siz[i]);
}
return;
};
auto findrt = [&](int x) {
p.clear(), p1.clear(), DFS1(x, -1);
int n = (int)p.size();
for (auto i : p)
if (mx[i] <= n / 2 && n - siz[i] <= n / 2)
return i;
return -1;
};
auto BFS = [&](int x) {
std::queue<int> q;
for (auto i : p1)
dis[i] = 0x3f3f3f3f;
q.push(x), dis[x] = 0;
for (; !q.empty(); ) {
int x = q.front();
q.pop();
for (auto i : _g[x])
if (dis[i] == 0x3f3f3f3f && now[i] == tik)
dis[i] = dis[x] + 1, q.push(i);
}
return;
};
std::function<void(int, int, int)> calc = [&](int x, int fa, int rt) {
for (auto i : t[x])
faa[i] = rt;
for (auto i : g[x])
if (i != fa && !tag[i])
calc(i, x, rt);
return;
};
std::vector<std::vector<std::tuple<int, int, int> > > tmp(n + 1);
std::function<void(int, std::vector<std::tuple<int, int, int> >)> DFS = [&](int x, std::vector<std::tuple<int, int, int> > q) {
if (q.empty())
return;
++tik, x = findrt(x);
for (auto i : g[x])
calc(i, x, i);
for (auto k : t[x])
if (!vis[k]) {
vis[k] = 1, BFS(k);
for (auto [u, v, id] : q)
res[id] = std::min(res[id], dis[u] + dis[v]);
}
for (auto [u, v, id] : q)
if (faa[u] == faa[v])
tmp[faa[u]].emplace_back(u, v, id);
std::vector<std::tuple<int, int, int> >().swap(q);
tag[x] = 1;
for (auto i : g[x])
if (!tag[i])
DFS(i, std::move(tmp[i]));
return;
};
DFS(1, std::move(u));
for (int i = 1; i <= q; ++i)
std::cout << res[i] << '\n';
return 0;
}C - Shopping
https://www.luogu.com.cn/problem/P6326
意识到连通块 DP 也是可以放在点分上做的，令 \(f_{u,i}\) 表示在（点分时的）子树 \(u\) 中，\(u\) 选了至少一个，共用了 \(i\) 体积的最大价值。剩下就是一个树上的多重 + 01 背包；发现这个 01 背包不满足可以优化的形式，所以考虑树上背包序列化，转换成序列上多重背包问题；不知道真实数据强度，但我认为应该用 单调队列优化多重背包。
注意树背包序列化的细节其实是有点多的。可能需要一些邪思。
#include <bits/stdc++.h>
const int inf = 0x3f3f3f3f;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int T;
for (std::cin >> T; T--; ) {
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int> > g(n + 1);
std::vector<int> v(n + 1), w(n + 1), c(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> w[i];
for (int i = 1; i <= n; ++i)
std::cin >> v[i];
for (int i = 1; i <= n; ++i)
std::cin >> c[i];
for (int i = 1, x, y; i < n; ++i) {
std::cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
}
std::vector<int> siz(n + 1), mx(n + 1), tag(n + 1), p;
std::function<void(int, int)> DFS1 = [&](int x, int fa) {
p.push_back(x);
siz[x] = 1, mx[x] = 0;
for (auto i : g[x])
if (i != fa && !tag[i]) {
DFS1(i, x);
siz[x] += siz[i];
mx[x] = std::max(mx[x], siz[i]);
}
return;
};
int now = 0;
std::vector<int> nex(n + 1), tab(n + 1);
auto findrt = [&](int x) {
p.clear(), DFS1(x, -1);
int n = (int)p.size();
for (auto i : p)
if (mx[i] <= n / 2 && n - siz[i] <= n / 2)
return i;
assert(0);
return -1;
};
std::function<void(int, int)> DFS2 = [&](int x, int fa) {
tab[++now] = x;
for (auto i : g[x])
if (i != fa && !tag[i])
DFS2(i, x);
nex[x] = now;
return;
};
int res = -inf;
std::function<void(int)> DFS = [&](int x) {
x = findrt(x), now = 0, DFS2(x, -1);
std::vector<std::vector<int> > f(now + 1, std::vector<int> (m + 1, -inf));
for (int i = 1; i <= c[x] && i * v[x] <= m; ++i)
f[1][i * v[x]] = i * w[x];
for (int i = 1; i < now; ++i) {
int V = v[tab[i + 1]], W = w[tab[i + 1]], C = c[tab[i + 1]];
for (int b = 0; b < V; ++b) {
std::vector<int> q;
int h = 0, t = -1;
for (int a = 0; a * V + b <= m; ++a) {
for (; h <= t && a - q[h] > C; ++h);
if (h <= t && f[i][q[h] * V + b] != -inf)
f[i + 1][a * V + b] = std::max(f[i + 1][a * V + b], f[i][q[h] * V + b] + (a - q[h]) * W);
for (; h <= t && f[i][a * V + b] - a * W >= f[i][q[t] * V + b] - q[t] * W; --t);
q.resize(++t + 1), q[t] = a;
}
}
int to = nex[tab[i + 1]];
for (int j = 0; j <= m; ++j)
f[to][j] = std::max(f[to][j], f[i][j]);
}
res = std::max(res, *std::max_element(f[now].begin(), f[now].end()));
std::vector<std::vector<int> >().swap(f);
tag[x] = 1;
for (auto i : g[x])
if (!tag[i])
DFS(i);
return;
};
DFS(1);
std::cout << res << '\n';
}
return 0;
}D - 加油站
https://www.luogu.com.cn/problem/P10805
点分治后分为 \(u\to rt\) 和 \(rt\to v\) 两个部分考虑。前者只需要倍增找到第一次加油的点即可；后者需要对于每个点作为加油站的情况，统计起点个数。
具体地，需要分类讨论：若 \(d(rt,v)<k\)，说明上次加油一定不在当前子树内；在根节点上登记的加油站中统计走得到 \(fa_v\) 但走不到 \(v\) 的，就可以找到 \(fa_v\) 作为加油站对应的起点个数。对 \(d(rt,v)\ge k\)，只需要倍增找到上一次加油的点即可找到 \(fa_v\) 的答案。
说着很轻巧，实现着很恶心。摆了。
E - 首都
https://www.luogu.com.cn/problem/P7215
启示我们点分治处理的问题不一是与『树结构』强相关者；也可以仅利用点分治划分出来的块，例如『若超出当前块，则一定不优』之类的。
本题的该性质通过分讨是好证的；所以直接每个块内暴力即可。复杂度 \(O(n\log n)\)。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, k;
std::cin >> n >> k;
std::vector<std::vector<int> > g(n + 1), t(k + 1);
for (int i = 1, x, y; i < n; ++i) {
std::cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
}
std::vector<int> col(n + 1), mx(n + 1), siz(n + 1);
for (int i = 1; i <= n; ++i) {
std::cin >> col[i];
t[col[i]].push_back(i);
}
std::vector<int> tag(n + 1), p, tik(n + 1), faa(n + 1), vis(n + 1), book(k + 1);
std::function<void(int, int)> DFS1 = [&](int x, int fa) {
siz[x] = 1, mx[x] = 0;
p.push_back(x), tik[x] = 1;
for (auto i : g[x])
if (!tag[i] && i != fa) {
DFS1(i, x);
siz[x] += siz[i];
mx[x] = std::max(mx[x], siz[i]);
}
return;
};
auto findrt = [&](int x) {
p.clear(), DFS1(x, -1);
int n = (int)p.size();
for (auto i : p)
if (mx[i] <= n / 2 && n - siz[i] <= n / 2)
return i;
assert(0);
return -1;
};
std::function<void(int)> DFS2 = [&](int x) {
for (auto i : g[x])
if (!tag[i] && i != faa[x])
faa[i] = x, DFS2(i);
return;
};
int res = 0x3f3f3f3f;
std::function<void(int)> DFS = [&](int x) {
x = findrt(x);
faa[x] = -1, DFS2(x);
std::queue<int> q;
q.push(col[x]), book[col[x]] = 1;
int cnt = 0;
for (; !q.empty(); ) {
int f = q.front();
q.pop();
for (auto i : t[f])
if (tik[i])
for (int p = i; ~p && !vis[p]; p = faa[p]) {
vis[p] = 1;
if (!book[col[p]]) {
if (++cnt >= res)
goto outo;
q.push(col[p]), book[col[p]] = 1;
}
}
else
goto outo;
}
res = cnt;
// printf("x = %d: cnt = %d\n", x, cnt);
outo:
for (auto i : p)
vis[i] = tik[i] = book[col[i]] = 0;
tag[x] = 1;
for (auto i : g[x])
if (!tag[i])
DFS(i);
return;
};
DFS(1);
std::cout << res << '\n';
return 0;
}F - 开店
https://www.luogu.com.cn/problem/P3241
转化问题，原问题即求解权值在 \([L,R]\) 间的元素到 \(u\) 的距离和。
一般求解距离的方法是找到 LCA 后计算，考虑如果不利用树上 LCA，而是利用点分树上 LCA 如何计算。分讨易证得点分树上 LCA 一定在两点路径上。
储存点分树上每个点到其每个祖先的距离，就可以方便地计算任意两点间距离。接下来处理原问题的弱化：对于每个 \(u\) 求解其到树上所有点距离和。显然这是一个类似换根的问题，随便做即可。
现在需要在线地解决原问题。可以用 vector 存储这一层所有点的权值与深度信息，按权值排序后二分查询。复杂度 \(O(n\log^2 n)\)。实现的时候应该可以注意到原题限制点度数对复杂度的保证。
打起来的时候感觉很史，但实际上调得比大多数题快。
大概懂得为什么经常看大佬写游记做到史题的实现预期都是『一遍过』了。
#include <bits/stdc++.h>
const long long inf = 1e18;
const int maxn = 1.5e5 + 5;
std::vector<std::pair<int, int> > g[maxn];
int top[maxn], siz[maxn], fa[maxn], son[maxn], dep[maxn], dis[maxn];
void DFS1(int x) {
siz[x] = 1;
for (auto [i, w] : g[x])
if (i != fa[x]) {
fa[i] = x;
dep[i] = dep[x] + 1, dis[i] = dis[x] + w;
DFS1(i);
siz[x] += siz[i];
if (siz[i] > siz[son[x]])
son[x] = i;
}
return;
}
void DFS2(int x) {
if (son[x])
top[son[x]] = top[x], DFS2(son[x]);
for (auto [i, w] : g[x])
if (i != fa[x] && i != son[x])
top[i] = i, DFS2(i);
return;
}
int ask(int x, int y) {
int sx = x, sy = y;
for (; top[x] != top[y]; x = fa[top[x]])
if (dep[top[x]] < dep[top[y]])
std::swap(x, y);
x = dep[x] < dep[y] ? x : y;
return dis[sx] + dis[sy] - 2 * dis[x];
}
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, q, A;
std::cin >> n >> q >> A;
std::vector<int> c(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> c[i];
for (int i = 1, x, y, w; i < n; ++i) {
std::cin >> x >> y >> w;
g[x].emplace_back(y, w), g[y].emplace_back(x, w);
}
DFS1(1), DFS2(1);
std::vector<int> mx(n + 1), siz(n + 1), p, tag(n + 1);
std::function<void(int, int)> DFS1 = [&](int x, int fa) {
siz[x] = 1, mx[x] = 0;
p.push_back(x);
for (auto [i, w] : g[x])
if (!tag[i] && i != fa) {
DFS1(i, x);
siz[x] += siz[i];
mx[x] = std::max(mx[x], siz[i]);
}
return;
};
auto findrt = [&](int x) {
p.clear(), DFS1(x, -1);
int n = (int)p.size();
for (auto i : p)
if (mx[i] <= n / 2 && n - siz[i] <= n / 2)
return i;
assert(0);
return -1;
};
std::vector<int> dis(n + 1);
std::vector<std::array<std::vector<std::pair<int, long long> >, 3> > t(n + 1);
std::function<void(int, int, std::vector<std::pair<int, long long> >&)> DFS2 = [&](int x, int fa, std::vector<std::pair<int, long long> > &t) {
t.emplace_back(c[x], dis[x]);
for (auto [i, w] : g[x])
if (!tag[i] && i != fa) {
dis[i] = dis[x] + w;
DFS2(i, x, t);
}
return;
};
std::vector<std::pair<int, int> > to(n + 1);
std::function<std::pair<int, int> (int)> DFS = [&](int x) {
x = findrt(x);
int ret = dis[x];
for (int j = 0; j < (int)g[x].size(); ++j) {
auto [i, w] = g[x][j];
if (!tag[i]) {
dis[i] = w;
DFS2(i, x, t[x][j]);
std::sort(t[x][j].begin(), t[x][j].end());
// printf("[%d, %d]: %d(%lld)", x, j, t[x][j][0].first, t[x][j][0].second);
for (int k = 1; k < (int)t[x][j].size(); ++k) {
t[x][j][k].second += t[x][j][k - 1].second;
// printf(" %d(%lld)", t[x][j][k].first, t[x][j][k].second);
}
// puts("");
}
}
tag[x] = 1;
for (int j = 0; j < (int)g[x].size(); ++j) {
auto [i, w] = g[x][j];
if (!tag[i]) {
auto [rt, d] = DFS(i);
to[rt] = { x, j };
}
}
return std::make_pair(x, ret);
};
int rt = DFS(1).first;
std::vector<std::vector<int> > fd(n + 1);
for (int i = 1; i <= n; ++i) {
int now = i;
for (;; now = to[now].first) {
fd[i].push_back(ask(now, i));
if (now == rt)
break;
}
}
for (int u, a, b; q--; ) {
static long long la = 0ll;
std::cin >> u >> a >> b;
int l = std::min((a + la) % A, (b + la) % A), r = std::max((a + la) % A, (b + la) % A);
// printf("ask %d, [%d, %d]\n", u, l, r);
auto ask = [&](int x, int j) {
auto res(0ll);
int cnt = 0, p = 0;
p = std::lower_bound(t[x][j].begin(), t[x][j].end(), std::make_pair(l, -1ll)) - t[x][j].begin();
cnt -= p;
if (p != 0)
res -= t[x][j][p - 1].second;
p = std::upper_bound(t[x][j].begin(), t[x][j].end(), std::make_pair(r, inf)) - t[x][j].begin();
cnt += p;
if (p != 0)
res += t[x][j][p - 1].second;
return std::make_pair(res, cnt);
};
la = ask(u, 0).first + ask(u, 1).first + ask(u, 2).first;
// int U = u;
for (auto d = ++fd[u].begin(); u != rt; ++d) {
auto [fa, k] = to[u];
// fprintf(stderr, "u = %d, fa = %d, d = %d\n", U, fa, *d);
for (int j = 0; j < 3; ++j)
if (j != k) {
auto [len, cnt] = ask(fa, j);
la += len + (long long)cnt * *d;
}
if (c[fa] >= l && c[fa] <= r)
la += *d;
u = fa;
}
std::cout << la << '\n';
}
return 0;
}