想起去年在考场上完全没有思路不想写数据结构于是骗了30分。现在想想当初还是naive。

 

这题看上去就是点分治。因为要动态加点所以要动态。然后利用替罪羊树的方法重构树上的一团东西（不能叫团，否则命名重复了）。

 

本来以为要写很久，结果也没写多久。奇怪的是，把maintain展开到insert里面之后就跑得飞快了，否则过不到而且根本跑不下来9和10。又丑了郁闷。

 

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>

using namespace std;


const int buf_len = 4000;
const size_t buf_size = buf_len * sizeof(char);
char buf[buf_len], *bufb(buf), *bufe(buf + 1);
#define readBuf() { 

if (++ bufb == bufe) 

bufe = (bufb = buf) + fread(buf, 1, buf_size, stdin); 

}
#define readInt(x) { 

register int s(0); 

do { 

readBuf(); 

} while (!isdigit(*bufb)); 

do { 

s = s * 10 + *bufb - 48; 

readBuf(); 

} while (isdigit(*bufb)); 

x = s; 

}


struct edge {
int t, v;
edge *next;
};
struct sbt_node {
int vl, sz;
sbt_node *ls, *rs;
};


typedef long long dint;


#ifdef WIN32
#define lld “%I64d”
#else
#define lld “%lld”
#endif
#define _l (long long int)


const int maxn = 100009;
const int fmod = 1e9;
const int maxl = 19;
const int maxnd = maxn * maxl * 2;
const int balc = 3;
const double ublim = 0.9;
const int inf = 0x3f3f3f3f;


dint lans;
int n;
int ath[maxn][maxl], drt[maxn], dep[maxn];
int bd[maxn], bsz[maxn], bfa[maxn], br[maxn], r[maxn];
int stsz[maxn], vis[maxn], vist;
sbt_node slst[maxnd], *sstc[maxnd], **sp, *brt[maxn], *prt[maxn];
edge *head[maxn], elst[maxn << 1], *ep(elst);


void pre() {
for (int i = 0; i < maxnd; ++ i) {
sstc[i] = slst + i;
slst[i]. ls = slst[i]. rs = 0;
}
sp = sstc;
vist = 0;
memset(vis, 0, sizeof(vis));
}


inline void addEdge(int u, int v, int w) {
ep-> t = v;
ep-> v = w;
ep-> next = head[u];
head[u] = ep ++;
}


#define szof(p) ((p)?(p->sz):0)
inline sbt_node* allocNode() {
static sbt_node* ret;
ret = (sp ++);
if (ret-> ls)
(– sp) = ret-> ls;
if (ret-> rs)
(– sp) = ret-> rs;
return ret;
}
inline void lRot(sbt_node &p) {
register sbt_node q(p-> ls);
p-> ls = q-> rs;
q-> rs = p;
q-> sz = p-> sz;
p-> sz = szof(p-> ls) + szof(p-> rs) + 1;
p = q;
}
inline void rRot(sbt_node &p) {
register sbt_node* q(p-> rs);
p-> rs = q-> ls;
q-> ls = p;
q-> sz = p-> sz;
p-> sz = szof(p-> ls) + szof(p-> rs) + 1;
p = q;
}
inline void sbtIns(sbt_node* &p, int v0) {
if (!p) {
p = allocNode();
p-> ls = p-> rs = 0;
p-> sz = 1;
p-> vl = v0;
}
else {
++ p-> sz;
if (v0 < p-> vl) {
sbtIns(p-> ls, v0);
if (szof(p-> ls) > szof(p-> rs) + balc)
lRot(p);
}
else {
sbtIns(p-> rs, v0);
if (szof(p-> ls) + balc < szof(p-> rs))
rRot(p);
}
}
}
int sbtCntLower(sbt_node* p, int v0) {
int s(0);
while (p)
if (v0 < p-> vl)
p = p-> ls;
else
s += szof(p-> ls) + 1, p = p-> rs;
return s;
}


int LCA(int u, int v) {
if (dep[u] < dep[v])
swap(u, v);
for (int i = maxl - 1; i >= 0; – i)
if (dep[ath[u][i]] >= dep[v])
u = ath[u][i];
if (u == v)
return u;
for (int i = maxl - 1; i >= 0; – i)
if (ath[u][i] ^ ath[v][i]) {
u = ath[u][i];
v = ath[v][i];
}
return ath[u][0];
}
inline int dist(int u, int v) {
int a(LCA(u, v));
return drt[u] + drt[v] - drt[a] * 2;
}


void insEach(sbt_node* q, sbt_node* &x, int mn) {
static sbt_node* stc[maxn];
int tst(1);
stc[1] = q;
while (tst) {
sbt_node* p(stc[tst –]);
sbtIns(x, p-> vl + mn);
if (p-> ls)
stc[++ tst] = p-> ls;
if (p-> rs)
stc[++ tst] = p-> rs;
}
}
int build(int pbd, int pbr, int pbf) {
static int q[maxn], fr[maxn], dst[maxn];
int hd(0), tl(1), ct(0), cs(inf);
q[0] = pbr;
fr[pbr] = 0;
dst[pbr] = 0;
while (hd < tl) {
int p(q[hd ++]);
for (edge* e = head[p]; e; e = e-> next)
if (bd[e-> t] == inf && e-> t != fr[p]) {
fr[e-> t] = p;
dst[e-> t] = dst[p] + e-> v;
q[tl ++] = e-> t;
}
}
for (int ti = tl - 1, p; ti >= 0; – ti) {
int ms(1);
p = q[ti];
stsz[p] = 1;
for (edge* e = head[p]; e; e = e-> next)
if (bd[e-> t] == inf && e-> t != fr[p]) {
stsz[p] += stsz[e-> t];
if (ms < stsz[e-> t])
ms = stsz[e-> t];
}
if (ms < tl - stsz[p])
ms = tl - stsz[p];
if (ms < cs) {
cs = ms;
ct = p;
}
}
for (int ti = 0, p; ti < tl; ++ ti) {
p = q[ti];
sbtIns(prt[ct], dst[p] - r[p]);
}
bd[ct] = pbd;
bsz[ct] = tl;
bfa[ct] = pbf;
br[ct] = pbr;
sbtIns(brt[ct], -r[ct]);
for (edge* e = head[ct]; e; e = e-> next)
if (bd[e-> t] == inf) {
int nr(build(pbd + 1, e-> t, ct));
insEach(prt[nr], brt[ct], e-> v);
}
return ct;
}


void rebuild(int p0, int pbd, int pbr, int pbf) {
static int q[maxn];
int hd(0), tl(1);
++ vist;
vis[p0] = vist;
q[0] = p0;
while (hd < tl) {
int p(q[hd ++]);
*(– sp) = brt[p];
(– sp) = prt[p];
brt[p] = 0;
prt[p] = 0;
for (edge e = head[p]; e; e = e-> next)
if (bd[e-> t] > pbd && vis[e-> t] < vist) {
vis[e-> t] = vist;
q[tl ++] = e-> t;
}
}
for (int i = 0; i < tl; ++ i)
bd[q[i]] = inf;
build(pbd, pbr, pbf);
}


void addNode(int p) {
brt[p] = 0;
sbtIns(brt[p], -r[p]);
prt[p] = 0;
sbtIns(prt[p], -r[p]);
if (p == 1) {
bd[p] = 1;
bsz[p] = 1;
bfa[p] = 0;
br[p] = 1;
}
else {
register int fa(ath[p][0]);
bd[p] = bd[fa] + 1;
bsz[p] = 1;
bfa[p] = fa;
br[p] = p;
int q(fa), l(p), ubp, dt(0);
double ubv(0);
while (q) {
++ bsz[q];
if ((double)bsz[l] / bsz[q] > ubv) {
ubv = (double)bsz[l] / bsz[q];
ubp = q;
}
int d0(dist(p, q));
sbtIns(brt[q], d0 - r[p]);
sbtIns(prt[q], dist(br[q], p) - r[p]);
dt += sbtCntLower(brt[q], r[p] - d0) - sbtCntLower(prt[l], r[p] - d0 - dist(br[l], q));
l = q;
q = bfa[q];
}
lans += dt;
if (ubv > ublim)
rebuild(ubp, bd[ubp], br[ubp], bfa[ubp]);
}
}


int main() {
#ifndef ONLINE_JUDGE
freopen(“in.txt”, “r”, stdin);
#endif


pre();
readInt(n);
readInt(n);
lans = 0;
for (int i = 1; i &lt;= n; ++ i) {
	int fa;
	readInt(fa);
	readInt(drt[i]);
	readInt(r[i]);
	if (i &gt; 1) {
		fa ^= lans % fmod;
		dep[i] = dep[fa] + 1;
		addEdge(fa, i, drt[i]);
		addEdge(i, fa, drt[i]);
		drt[i] += drt[fa];
		ath[i][0] = fa;
		for (int j = 1; j &lt; maxl; ++ j)
			ath[i][j] = ath[ath[i][j - 1]][j - 1];
	}
	else {
		dep[i] = 1;
	}
	addNode(i);
	printf(lld "\n", lans);
}



}