意外的好写.....
考虑点分
(dis(i, j) leq r_i + r_j)
对于过分治中心一点(u)，有
(dis(i, u) - r_i = dis(j, u) + r_j)
对于同一子树内需要去重
原本是考虑用值域线段树来维护的，看了看(10^9)的范围，空间估计开不下
那就用平衡树吧...
用动态点分来维护答案，每次默认把(i)归到父亲的分治结构中
如果某个分治结构过于不平衡，那么就暴力重构
注意一下，一个点分治中的分治结构在树中对应一个联通块，没有任何其他的性质...
（我用(n log n)的时间直接暴力维护了，感觉应该有更好的办法）
和二叉树的分析差不多，复杂度是(O(n log^2 n))的吧...
一开始受到了打树静态的动态点分治的影响
对于分治中心(u)，直接把每个子树的信息存在了和(u)有对应连边的点上...
事实上，应该存在对应子树的重心上，重构的时候才不会出错...
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define ri register int
#define rep(io, st, ed) for(ri io = st; io <= ed; io ++)
#define drep(io, ed, st) for(ri io = ed; io >= st; io --)
#define gc getchar
inline int read() {
int p = 0, w = 1; char c = gc();
while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); }
while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc();
return p * w;
}
const int sid = 3e5 + 5;
const int cid = 5e6 + 5;
struct stO_Mxl_Orz {
int trash[cid], id, top;
struct Yume_Alive_Forever {
int sz, pri, num, son[2];
ll val;
} t[cid];
inline int rand() {
static int seed = 23333333;
return seed = (seed * 97103LL) % 2147483647;
}
#define ls(o) t[(o)].son[0]
#define rs(o) t[(o)].son[1]
inline int newnode(ll v) {
int ip = top ? trash[top --] : ++ id;
ls(ip) = rs(ip) = 0; t[ip].sz = t[ip].num = 1;
t[ip].val = v; t[ip].pri = rand();
return ip;
}
inline void upd(int o) {
t[o].sz = t[ls(o)].sz + t[rs(o)].sz + t[o].num;
}
inline void recycle(int &o) {
if(!o) return;
recycle(ls(o)); recycle(rs(o));
trash[++ top] = o;
}
inline void rotate(int &o, int p) {
int u = t[o].son[p];
t[o].son[p] = t[u].son[!p]; t[u].son[!p] = o;
upd(o); upd(u); o = u;
}
inline void insert(int &o, ll v) {
if(!o) { o = newnode(v); return; }
t[o].sz ++;
if(v == t[o].val) { t[o].num ++; return; }
int nxt = v > t[o].val;
insert(t[o].son[nxt], v);
if(t[o].pri > t[t[o].son[nxt]].pri) rotate(o, nxt);
}
inline int qry(int o, ll v) {
if(!o) return 0;
if(v == t[o].val) return t[ls(o)].sz + t[o].num;
if(v < t[o].val) return qry(ls(o), v);
else return t[ls(o)].sz + t[o].num + qry(rs(o), v);
}
} myk;
bool debug;
ll dit[sid];
int dep[sid], up[sid][17];
inline int lca(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
int d = dep[u] - dep[v];
drep(i, 16, 0) if(d & (1 << i)) u = up[u][i];
if(u == v) return u;
drep(i, 16, 0)
if(up[u][i] != up[v][i]) u = up[u][i], v = up[v][i];
if(u == v) return u;
return up[u][0];
}
inline ll dis(int u, int v) {
return dit[u] + dit[v] - (dit[lca(u, v)] << 1);
}
ll ans;
int r[sid], fa[sid];
int msx[sid], fd[sid], rt[sid], lrt[sid];
int asz, cnp, tim, hrt, ban;
int son[sid], sz[sid], ok[sid], vis[sid];
int cap[sid], nxt[sid], node[sid], len[sid];
inline void addedge(int u, int v, int w) {
nxt[++ cnp] = cap[u]; cap[u] = cnp; node[cnp] = v; len[cnp] = w;
nxt[++ cnp] = cap[v]; cap[v] = cnp; node[cnp] = u; len[cnp] = w;
}
#define cur node[i]
inline void grt(int o, int fa) {
son[o] = 0; sz[o] = 1;
for(int i = cap[o]; i; i = nxt[i])
if(ok[cur] == tim && vis[cur] != tim && cur != fa) {
grt(cur, o); sz[o] += sz[cur];
if(sz[cur] > son[o]) son[o] = sz[cur];
}
son[o] = max(son[o], asz - son[o]);
if(son[o] < son[hrt]) hrt = o;
}
inline void dfs(int o, int fa) {
sz[o] = 1;
for(int i = cap[o]; i; i = nxt[i])
if(ok[cur] == tim && vis[cur] != tim && cur != fa)
dfs(cur, o), sz[o] += sz[cur];
}
vector <int> as[sid];
inline void dfs(int o, int fa, int anc1, int anc2, ll lev) {
as[anc2].push_back(o);
myk.insert(rt[anc2], lev - r[o]);
myk.insert(lrt[anc1], lev - r[o]);
for(int i = cap[o]; i; i = nxt[i])
if(ok[cur] == tim && vis[cur] != tim && cur != fa)
dfs(cur, o, anc1, anc2, lev + len[i]);
}
inline void solve(int o) {
vis[o] = tim;
as[o].push_back(o);
myk.insert(rt[o], - r[o]);
for(int i = cap[o]; i; i = nxt[i])
if(ok[cur] == tim && vis[cur] != tim && cur != ban) dfs(cur, o);
msx[o] = 0;
for(int i = cap[o]; i; i = nxt[i])
if(ok[cur] == tim && vis[cur] != tim) {
msx[o] = max(msx[o], sz[cur]);
asz = sz[cur]; hrt = 0;
grt(cur, o); fd[hrt] = o;
dfs(cur, o, hrt, o, len[i]);
solve(hrt);
}
}
inline void dfs(int o, int fa, int anc) {
as[o].clear();
myk.recycle(rt[o]); rt[o] = 0;
myk.recycle(lrt[o]); lrt[o] = 0;
if(ban) myk.insert(lrt[anc], dis(o, ban) - r[o]);
for(int i = cap[o]; i; i = nxt[i])
if(ok[cur] == tim && cur != ban && cur != fa)
dfs(cur, o, anc);
}
inline void rebuild(int o) {
++ tim; ban = fd[o];
asz = myk.t[rt[o]].sz; hrt = 0;
for(auto x : as[o]) ok[x] = tim;
grt(o, ban);
dfs(hrt, ban, hrt);
fd[hrt] = ban;
solve(hrt);
}
inline void modify(int o) {
fd[o] = fa[o];
for(ri now = fd[o], lst = o; now; lst = now, now = fd[now]) {
ll v = dis(now, o);
as[now].push_back(o);
myk.insert(rt[now], v - r[o]);
myk.insert(lrt[lst], v - r[o]);
ans += myk.qry(rt[now], r[o] - v) - myk.qry(lrt[lst], r[o] - v);
msx[now] = max(msx[now], myk.t[lrt[lst]].sz);
}
const double Yume_Saiko = 0.756412;
int tmp = -1;
for(ri now = fd[o]; now; now = fd[now])
if(msx[now] >= myk.t[rt[now]].sz * Yume_Saiko) tmp = now;
if(tmp != -1) rebuild(tmp);
}
const int mod = 1e9;
int main() {
int Wahaha = read();
int n = read(); son[0] = n + 1;
for(ri i = 1; i <= n; i ++) {
fa[i] = read() ^ (ans % mod);
int c = read(); r[i] = read();
addedge(fa[i], i, c);
up[i][0] = fa[i];
dep[i] = dep[fa[i]] + 1;
dit[i] = dit[fa[i]] + c;
for(ri j = 1; j <= 16; j ++)
up[i][j] = up[up[i][j - 1]][j - 1];
as[i].push_back(i);
myk.insert(rt[i], -r[i]);
if(i != 1) modify(i);
printf("%lld
", ans);
}
return 0;
}